OBDH SD Implementation

This page is here to explain some choices in the sd card implementation.

Hashing algorithm

If the power is cycled during an sd write, the sd card will not mark which part has been correctly written, in fact it leaves it in such a position that we don't know if a sector has been written. We have a variety of possible solutions to this, we could either write a value out to signify that the data has been correctly written - which has the down side that it might still be present on the sd card sector from a previous write, we could zero out the sd card before writing - but during the zeroing out the power could be cycled, or we could use a hashing algorithm.

There are many varieties of hashing algorithms, from the infamous cyclic redundancy check (CRC) to the likes of the MD5 hash. These have been designed to run as quickly and effectively as possible on many processors including the x86 found in the majority of computers but wouldn't fair too well on a 16bit mcu with a limited memory space. The hash generated by MD5 is 128bit. To save time and space, other less perfect1 hashes have been found.

The choices are:

1 a modified Bernstein hash


The original Bernstein hash uses an addition instead of an xor.

2 a shift-add-xor hash

3 Fowler/Noll/Vo (FNV) hash

4 One at a time hash

5 ELF hash

The output from both the FNV hash and the one at a time hash were too long for practical use.

The 3 remaining hashes, mb, sax and elf, were then ported over to c where they were compiled with full optimisation and loop unrolling. This gave an idea at the workload involved with each function.

  • mb had the smallest code size with a total runtime of 324 instructions (67 instructions in the function with a 5 repeat loop inside)
  • sax had a total runtime of 439 instructions (91 instructions in the function with a 5 repeat loop inside)
  • elf had a total runtime of the order of 900 instructions (183 instructions in function with a 5 repeat loop and several conditional jumps)

From this analysis it seems that the best hashing function for speed is the modified Bernstein algorithm (on a basis that each instruction takes the same amount of time to run). The functions were first tested in python before disassembly, which showed the modified Bernstein, on average, performing quicker than sax and elf. The source code is included for completeness.

References

Algorithms from http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.