sphinx.addnodesdocument)}( rawsourcechildren]( translations LanguagesNode)}(hhh](h pending_xref)}(hhh]docutils.nodesTextChinese (Simplified)}parenthsba attributes}(ids]classes]names]dupnames]backrefs] refdomainstdreftypedoc reftarget+/translations/zh_CN/driver-api/mtd/nand_eccmodnameN classnameN refexplicitutagnamehhh ubh)}(hhh]hChinese (Traditional)}hh2sbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget+/translations/zh_TW/driver-api/mtd/nand_eccmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hItalian}hhFsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget+/translations/it_IT/driver-api/mtd/nand_eccmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hJapanese}hhZsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget+/translations/ja_JP/driver-api/mtd/nand_eccmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hKorean}hhnsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget+/translations/ko_KR/driver-api/mtd/nand_eccmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hPortuguese (Brazilian)}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget+/translations/pt_BR/driver-api/mtd/nand_eccmodnameN classnameN refexplicituh1hhh ubh)}(hhh]hSpanish}hhsbah}(h]h ]h"]h$]h&] refdomainh)reftypeh+ reftarget+/translations/sp_SP/driver-api/mtd/nand_eccmodnameN classnameN refexplicituh1hhh ubeh}(h]h ]h"]h$]h&]current_languageEnglishuh1h hh _documenthsourceNlineNubhsection)}(hhh](htitle)}(hNAND Error-correction Codeh]hNAND Error-correction Code}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhE/var/lib/git/docbuild/linux/Documentation/driver-api/mtd/nand_ecc.rsthKubh)}(hhh](h)}(h Introductionh]h Introduction}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhhhhhKubh paragraph)}(hXPHaving looked at the linux mtd/nand Hamming software ECC engine driver I felt there was room for optimisation. I bashed the code for a few hours performing tricks like table lookup removing superfluous code etc. After that the speed was increased by 35-40%. Still I was not too happy as I felt there was additional room for improvement.h]hXPHaving looked at the linux mtd/nand Hamming software ECC engine driver I felt there was room for optimisation. I bashed the code for a few hours performing tricks like table lookup removing superfluous code etc. After that the speed was increased by 35-40%. Still I was not too happy as I felt there was additional room for improvement.}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhhhubh)}(hBad! I was hooked. I decided to annotate my steps in this file. Perhaps it is useful to someone or someone learns something from it.h]hBad! I was hooked. I decided to annotate my steps in this file. Perhaps it is useful to someone or someone learns something from it.}(hhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhhhhubeh}(h] introductionah ]h"] introductionah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(h The problemh]h The problem}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hNAND flash (at least SLC one) typically has sectors of 256 bytes. However NAND flash is not extremely reliable so some error detection (and sometimes correction) is needed.h]hNAND flash (at least SLC one) typically has sectors of 256 bytes. However NAND flash is not extremely reliable so some error detection (and sometimes correction) is needed.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hX This is done by means of a Hamming code. I'll try to explain it in laymans terms (and apologies to all the pro's in the field in case I do not use the right terminology, my coding theory class was almost 30 years ago, and I must admit it was not one of my favourites).h]hXThis is done by means of a Hamming code. I’ll try to explain it in laymans terms (and apologies to all the pro’s in the field in case I do not use the right terminology, my coding theory class was almost 30 years ago, and I must admit it was not one of my favourites).}(hj!hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXpAs I said before the ecc calculation is performed on sectors of 256 bytes. This is done by calculating several parity bits over the rows and columns. The parity used is even parity which means that the parity bit = 1 if the data over which the parity is calculated is 1 and the parity bit = 0 if the data over which the parity is calculated is 0. So the total number of bits over the data over which the parity is calculated + the parity bit is even. (see wikipedia if you can't follow this). Parity is often calculated by means of an exclusive or operation, sometimes also referred to as xor. In C the operator for xor is ^h]hXrAs I said before the ecc calculation is performed on sectors of 256 bytes. This is done by calculating several parity bits over the rows and columns. The parity used is even parity which means that the parity bit = 1 if the data over which the parity is calculated is 1 and the parity bit = 0 if the data over which the parity is calculated is 0. So the total number of bits over the data over which the parity is calculated + the parity bit is even. (see wikipedia if you can’t follow this). Parity is often calculated by means of an exclusive or operation, sometimes also referred to as xor. In C the operator for xor is ^}(hj/hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(h'Back to ecc. Let's give a small figure:h]h)Back to ecc. Let’s give a small figure:}(hj=hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK)hjhhubhtable)}(hhh]htgroup)}(hhh](hcolspec)}(hhh]h}(h]h ]h"]h$]h&]colwidthK uh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhjRubhtbody)}(hhh](hrow)}(hhh](hentry)}(hhh]h)}(h byte 0:h]h byte 0:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit7h]hbit7}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit6h]hbit6}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit5h]hbit5}(hj7hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hj4ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit4h]hbit4}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjKubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit3h]hbit3}(hjehhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjbubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit2h]hbit2}(hj|hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjyubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit1h]hbit1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit0h]hbit0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp0h]hrp0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp2h]hrp2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp4h]hrp4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h...h]h...}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp14h]hrp14}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK-hjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h byte 1:h]h byte 1:}(hj=hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hj:ubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit7h]hbit7}(hjThhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjQubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit6h]hbit6}(hjkhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjhubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit5h]hbit5}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit4h]hbit4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit3h]hbit3}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit2h]hbit2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit1h]hbit1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hbit0h]hbit0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hrp1h]hrp1}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hj ubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hrp2h]hrp2}(hj#hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hj ubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hrp4h]hrp4}(hj:hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hj7ubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(h...h]h...}(hjQhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjNubah}(h]h ]h"]h$]h&]uh1jhj7ubj)}(hhh]h)}(hrp14h]hrp14}(hjhhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK.hjeubah}(h]h ]h"]h$]h&]uh1jhj7ubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h byte 2:h]h byte 2:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit7h]hbit7}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit6h]hbit6}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit5h]hbit5}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit4h]hbit4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit3h]hbit3}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit2h]hbit2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit1h]hbit1}(hj)hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hj&ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit0h]hbit0}(hj@hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hj=ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp0h]hrp0}(hjWhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjTubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp3h]hrp3}(hjnhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjkubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp4h]hrp4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h...h]h...}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp14h]hrp14}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK/hjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h byte 3:h]h byte 3:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit7h]hbit7}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit6h]hbit6}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit5h]hbit5}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit4h]hbit4}(hj/hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hj,ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit3h]hbit3}(hjFhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjCubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit2h]hbit2}(hj]hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjZubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit1h]hbit1}(hjthhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjqubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit0h]hbit0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp1h]hrp1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp3h]hrp3}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp4h]hrp4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h...h]h...}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp14h]hrp14}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK0hjubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h byte 4:h]h byte 4:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit7h]hbit7}(hj5hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hj2ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit6h]hbit6}(hjLhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjIubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit5h]hbit5}(hjchhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hj`ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit4h]hbit4}(hjzhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjwubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit3h]hbit3}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit2h]hbit2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit1h]hbit1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit0h]hbit0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp0h]hrp0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp2h]hrp2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp5h]hrp5}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h...h]h...}(hj2hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hj/ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp14h]hrp14}(hjIhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK1hjFubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h...h]h...}(hjihhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK2hjfubah}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubj)}(hhh]h}(h]h ]h"]h$]h&]uh1jhjcubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h byte 254:h]h byte 254:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit7h]hbit7}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit6h]hbit6}(hj, hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj) ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit5h]hbit5}(hjC hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj@ ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit4h]hbit4}(hjZ hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hjW ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit3h]hbit3}(hjq hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hjn ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit2h]hbit2}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit1h]hbit1}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hbit0h]hbit0}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp0h]hrp0}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp3h]hrp3}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp5h]hrp5}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(h...h]h...}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hrp15h]hrp15}(hj) hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK3hj& ubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh](j)}(hhh]h)}(h byte 255:h]h byte 255:}(hjI hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hjF ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit7 cp1 cp3 cp5h]hbit7 cp1 cp3 cp5}(hj` hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj] ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit6 cp0 cp3 cp5h]hbit6 cp0 cp3 cp5}(hjw hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hjt ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit5 cp1 cp2 cp5h]hbit5 cp1 cp2 cp5}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit4 cp0 cp2 cp5h]hbit4 cp0 cp2 cp5}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit3 cp1 cp3 cp4h]hbit3 cp1 cp3 cp4}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit2 cp0 cp3 cp4h]hbit2 cp0 cp3 cp4}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit1 cp1 cp2 cp4h]hbit1 cp1 cp2 cp4}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hbit0 cp0 cp2 cp4h]hbit0 cp0 cp2 cp4}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hrp1h]hrp1}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hrp3h]hrp3}(hj/ hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hj, ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hrp5h]hrp5}(hjF hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hjC ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(h...h]h...}(hj] hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hjZ ubah}(h]h ]h"]h$]h&]uh1jhjC ubj)}(hhh]h)}(hrp15h]hrp15}(hjt hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK4hjq ubah}(h]h ]h"]h$]h&]uh1jhjC ubeh}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjRubeh}(h]h ]h"]h$]h&]colsKuh1jPhjMubah}(h]h ]h"]h$]h&]uh1jKhjhhhhhNubh)}(hiThis figure represents a sector of 256 bytes. cp is my abbreviation for column parity, rp for row parity.h]hiThis figure represents a sector of 256 bytes. cp is my abbreviation for column parity, rp for row parity.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK:hjhhubh)}(h%Let's start to explain column parity.h]h'Let’s start to explain column parity.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK=hjhhubh bullet_list)}(hhh]h list_item)}(hcp0 is the parity that belongs to all bit0, bit2, bit4, bit6. so the sum of all bit0, bit2, bit4 and bit6 values + cp0 itself is even. h](h)}(h=cp0 is the parity that belongs to all bit0, bit2, bit4, bit6.h]h=cp0 is the parity that belongs to all bit0, bit2, bit4, bit6.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK?hj ubh)}(hHso the sum of all bit0, bit2, bit4 and bit6 values + cp0 itself is even.h]hHso the sum of all bit0, bit2, bit4 and bit6 values + cp0 itself is even.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKAhj ubeh}(h]h ]h"]h$]h&]uh1j hj hhhhhNubah}(h]h ]h"]h$]h&]bullet-uh1j hhhK?hjhhubh)}(h:Similarly cp1 is the sum of all bit1, bit3, bit5 and bit7.h]h:Similarly cp1 is the sum of all bit1, bit3, bit5 and bit7.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKChjhhubj )}(hhh](j )}(h0cp2 is the parity over bit0, bit1, bit4 and bit5h]h)}(hj h]h0cp2 is the parity over bit0, bit1, bit4 and bit5}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKEhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(h1cp3 is the parity over bit2, bit3, bit6 and bit7.h]h)}(hj h]h1cp3 is the parity over bit2, bit3, bit6 and bit7.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKFhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(h1cp4 is the parity over bit0, bit1, bit2 and bit3.h]h)}(hj3 h]h1cp4 is the parity over bit0, bit1, bit2 and bit3.}(hj5 hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKGhj1 ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(h2cp5 is the parity over bit4, bit5, bit6 and bit7. h]h)}(h1cp5 is the parity over bit4, bit5, bit6 and bit7.h]h1cp5 is the parity over bit4, bit5, bit6 and bit7.}(hjL hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKHhjH ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubeh}(h]h ]h"]h$]h&]j j uh1j hhhKEhjhhubh)}(h0Note that each of cp0 .. cp5 is exactly one bit.h]h0Note that each of cp0 .. cp5 is exactly one bit.}(hjf hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKJhjhhubh)}(h*Row parity actually works almost the same.h]h*Row parity actually works almost the same.}(hjt hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKLhjhhubj )}(hhh](j )}(h>rp0 is the parity of all even bytes (0, 2, 4, 6, ... 252, 254)h]h)}(hj h]h>rp0 is the parity of all even bytes (0, 2, 4, 6, ... 252, 254)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKNhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(h>rp1 is the parity of all odd bytes (1, 3, 5, 7, ..., 253, 255)h]h)}(hj h]h>rp1 is the parity of all odd bytes (1, 3, 5, 7, ..., 253, 255)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKOhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(h^rp2 is the parity of all bytes 0, 1, 4, 5, 8, 9, ... (so handle two bytes, then skip 2 bytes).h]h)}(h^rp2 is the parity of all bytes 0, 1, 4, 5, 8, 9, ... (so handle two bytes, then skip 2 bytes).h]h^rp2 is the parity of all bytes 0, 1, 4, 5, 8, 9, ... (so handle two bytes, then skip 2 bytes).}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKPhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(hIrp3 is covers the half rp2 does not cover (bytes 2, 3, 6, 7, 10, 11, ...)h]h)}(hj h]hIrp3 is covers the half rp2 does not cover (bytes 2, 3, 6, 7, 10, 11, ...)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKRhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(hfor rp4 the rule is cover 4 bytes, skip 4 bytes, cover 4 bytes, skip 4 etc. so rp4 calculates parity over bytes 0, 1, 2, 3, 8, 9, 10, 11, 16, ...)h](h)}(hKfor rp4 the rule is cover 4 bytes, skip 4 bytes, cover 4 bytes, skip 4 etc.h]hKfor rp4 the rule is cover 4 bytes, skip 4 bytes, cover 4 bytes, skip 4 etc.}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKShj ubh)}(hFso rp4 calculates parity over bytes 0, 1, 2, 3, 8, 9, 10, 11, 16, ...)h]hFso rp4 calculates parity over bytes 0, 1, 2, 3, 8, 9, 10, 11, 16, ...)}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKUhj ubeh}(h]h ]h"]h$]h&]uh1j hj hhhhhNubj )}(hKand rp5 covers the other half, so bytes 4, 5, 6, 7, 12, 13, 14, 15, 20, .. h]h)}(hJand rp5 covers the other half, so bytes 4, 5, 6, 7, 12, 13, 14, 15, 20, ..h]hJand rp5 covers the other half, so bytes 4, 5, 6, 7, 12, 13, 14, 15, 20, ..}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKVhj ubah}(h]h ]h"]h$]h&]uh1j hj hhhhhNubeh}(h]h ]h"]h$]h&]j j uh1j hhhKNhjhhubh)}(h=The story now becomes quite boring. I guess you get the idea.h]h=The story now becomes quite boring. I guess you get the idea.}(hj& hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKXhjhhubj )}(hhh](j )}(h#rp6 covers 8 bytes then skips 8 etch]h)}(hj9 h]h#rp6 covers 8 bytes then skips 8 etc}(hj; hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKZhj7 ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h#rp7 skips 8 bytes then covers 8 etch]h)}(hjP h]h#rp7 skips 8 bytes then covers 8 etc}(hjR hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK[hjN ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h%rp8 covers 16 bytes then skips 16 etch]h)}(hjg h]h%rp8 covers 16 bytes then skips 16 etc}(hji hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK\hje ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h%rp9 skips 16 bytes then covers 16 etch]h)}(hj~ h]h%rp9 skips 16 bytes then covers 16 etc}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK]hj| ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h&rp10 covers 32 bytes then skips 32 etch]h)}(hj h]h&rp10 covers 32 bytes then skips 32 etc}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK^hj ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h&rp11 skips 32 bytes then covers 32 etch]h)}(hj h]h&rp11 skips 32 bytes then covers 32 etc}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK_hj ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h&rp12 covers 64 bytes then skips 64 etch]h)}(hj h]h&rp12 covers 64 bytes then skips 64 etc}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK`hj ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h&rp13 skips 64 bytes then covers 64 etch]h)}(hj h]h&rp13 skips 64 bytes then covers 64 etc}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKahj ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h$rp14 covers 128 bytes then skips 128h]h)}(hj h]h$rp14 covers 128 bytes then skips 128}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKbhj ubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubj )}(h%rp15 skips 128 bytes then covers 128 h]h)}(h$rp15 skips 128 bytes then covers 128h]h$rp15 skips 128 bytes then covers 128}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKchjubah}(h]h ]h"]h$]h&]uh1j hj4 hhhhhNubeh}(h]h ]h"]h$]h&]j j uh1j hhhKZhjhhubh)}(hJIn the end the parity bits are grouped together in three bytes as follows:h]hJIn the end the parity bits are grouped together in three bytes as follows:}(hj$hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKehjhhubjL)}(hhh]jQ)}(hhh](jV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubjV)}(hhh]h}(h]h ]h"]h$]h&]colwidthKuh1jUhj5ubhthead)}(hhh]j)}(hhh](j)}(hhh]h)}(hECCh]hECC}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 7h]hBit 7}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 6h]hBit 6}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 5h]hBit 5}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 4h]hBit 4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihjubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 3h]hBit 3}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihj ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 2h]hBit 2}(hj'hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihj$ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 1h]hBit 1}(hj>hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihj;ubah}(h]h ]h"]h$]h&]uh1jhjubj)}(hhh]h)}(hBit 0h]hBit 0}(hjUhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKihjRubah}(h]h ]h"]h$]h&]uh1jhjubeh}(h]h ]h"]h$]h&]uh1jhjubah}(h]h ]h"]h$]h&]uh1jhj5ubj)}(hhh](j)}(hhh](j)}(hhh]h)}(hECC 0h]hECC 0}(hj~hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhj{ubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp07h]hrp07}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp06h]hrp06}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp05h]hrp05}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp04h]hrp04}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp03h]hrp03}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp02h]hrp02}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp01h]hrp01}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhjubah}(h]h ]h"]h$]h&]uh1jhjxubj)}(hhh]h)}(hrp00h]hrp00}(hj6hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKkhj3ubah}(h]h ]h"]h$]h&]uh1jhjxubeh}(h]h ]h"]h$]h&]uh1jhjuubj)}(hhh](j)}(hhh]h)}(hECC 1h]hECC 1}(hjVhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjSubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp15h]hrp15}(hjmhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp14h]hrp14}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp13h]hrp13}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp12h]hrp12}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp11h]hrp11}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp10h]hrp10}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp09h]hrp09}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhjubah}(h]h ]h"]h$]h&]uh1jhjPubj)}(hhh]h)}(hrp08h]hrp08}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKlhj ubah}(h]h ]h"]h$]h&]uh1jhjPubeh}(h]h ]h"]h$]h&]uh1jhjuubj)}(hhh](j)}(hhh]h)}(hECC 2h]hECC 2}(hj.hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhj+ubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hcp5h]hcp5}(hjEhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjBubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hcp4h]hcp4}(hj\hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjYubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hcp3h]hcp3}(hjshhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjpubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hcp2h]hcp2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hcp1h]hcp1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hcp0h]hcp0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(h1h]h1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjubah}(h]h ]h"]h$]h&]uh1jhj(ubj)}(hhh]h)}(hjh]h1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKmhjubah}(h]h ]h"]h$]h&]uh1jhj(ubeh}(h]h ]h"]h$]h&]uh1jhjuubeh}(h]h ]h"]h$]h&]uh1jhj5ubeh}(h]h ]h"]h$]h&]colsK uh1jPhj2ubah}(h]h ]h"]h$]h&]uh1jKhjhhhhhNubh)}(hI detected after writing this that ST application note AN1823 (http://www.st.com/stonline/) gives a much nicer picture.(but they use line parity as term where I use row parity) Oh well, I'm graphically challenged, so suffer with me for a moment :-)h](h?I detected after writing this that ST application note AN1823 (}(hjhhhNhNubh reference)}(hhttp://www.st.com/stonline/h]hhttp://www.st.com/stonline/}(hjhhhNhNubah}(h]h ]h"]h$]h&]refurijuh1jhjubh) gives a much nicer picture.(but they use line parity as term where I use row parity) Oh well, I’m graphically challenged, so suffer with me for a moment :-)}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhKphjhhubh)}(hBAnd I could not reuse the ST picture anyway for copyright reasons.h]hBAnd I could not reuse the ST picture anyway for copyright reasons.}(hj5hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKuhjhhubeh}(h] the-problemah ]h"] the problemah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(h Attempt 0h]h Attempt 0}(hjNhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjKhhhhhKyubh)}(hGImplementing the parity calculation is pretty simple. In C pseudocode::h]hFImplementing the parity calculation is pretty simple. In C pseudocode:}(hj\hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhK{hjKhhubh literal_block)}(hXHfor (i = 0; i < 256; i++) { if (i & 0x01) rp1 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp1; else rp0 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp0; if (i & 0x02) rp3 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp3; else rp2 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp2; if (i & 0x04) rp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp5; else rp4 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp4; if (i & 0x08) rp7 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp7; else rp6 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp6; if (i & 0x10) rp9 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp9; else rp8 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp8; if (i & 0x20) rp11 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp11; else rp10 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp10; if (i & 0x40) rp13 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp13; else rp12 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp12; if (i & 0x80) rp15 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp15; else rp14 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp14; cp0 = bit6 ^ bit4 ^ bit2 ^ bit0 ^ cp0; cp1 = bit7 ^ bit5 ^ bit3 ^ bit1 ^ cp1; cp2 = bit5 ^ bit4 ^ bit1 ^ bit0 ^ cp2; cp3 = bit7 ^ bit6 ^ bit3 ^ bit2 ^ cp3 cp4 = bit3 ^ bit2 ^ bit1 ^ bit0 ^ cp4 cp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ cp5 }h]hXHfor (i = 0; i < 256; i++) { if (i & 0x01) rp1 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp1; else rp0 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp0; if (i & 0x02) rp3 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp3; else rp2 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp2; if (i & 0x04) rp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp5; else rp4 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp4; if (i & 0x08) rp7 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp7; else rp6 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp6; if (i & 0x10) rp9 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp9; else rp8 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp8; if (i & 0x20) rp11 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp11; else rp10 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp10; if (i & 0x40) rp13 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp13; else rp12 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp12; if (i & 0x80) rp15 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp15; else rp14 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ bit3 ^ bit2 ^ bit1 ^ bit0 ^ rp14; cp0 = bit6 ^ bit4 ^ bit2 ^ bit0 ^ cp0; cp1 = bit7 ^ bit5 ^ bit3 ^ bit1 ^ cp1; cp2 = bit5 ^ bit4 ^ bit1 ^ bit0 ^ cp2; cp3 = bit7 ^ bit6 ^ bit3 ^ bit2 ^ cp3 cp4 = bit3 ^ bit2 ^ bit1 ^ bit0 ^ cp4 cp5 = bit7 ^ bit6 ^ bit5 ^ bit4 ^ cp5 }}hjlsbah}(h]h ]h"]h$]h&] xml:spacepreserveuh1jjhhhK~hjKhhubeh}(h] attempt-0ah ]h"] attempt 0ah$]h&]uh1hhhhhhhhKyubh)}(hhh](h)}(h Analysis 0h]h Analysis 0}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubh)}(hC does have bitwise operators but not really operators to do the above efficiently (and most hardware has no such instructions either). Therefore without implementing this it was clear that the code above was not going to bring me a Nobel prize :-)h]hC does have bitwise operators but not really operators to do the above efficiently (and most hardware has no such instructions either). Therefore without implementing this it was clear that the code above was not going to bring me a Nobel prize :-)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hXnFortunately the exclusive or operation is commutative, so we can combine the values in any order. So instead of calculating all the bits individually, let us try to rearrange things. For the column parity this is easy. We can just xor the bytes and in the end filter out the relevant bits. This is pretty nice as it will bring all cp calculation out of the for loop.h]hXnFortunately the exclusive or operation is commutative, so we can combine the values in any order. So instead of calculating all the bits individually, let us try to rearrange things. For the column parity this is easy. We can just xor the bytes and in the end filter out the relevant bits. This is pretty nice as it will bring all cp calculation out of the for loop.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubh)}(hISimilarly we can first xor the bytes for the various rows. This leads to:h]hISimilarly we can first xor the bytes for the various rows. This leads to:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhKhjhhubeh}(h] analysis-0ah ]h"] analysis 0ah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(h Attempt 1h]h Attempt 1}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhKubjk)}(hX* const char parity[256] = { 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 }; void ecc1(const unsigned char *buf, unsigned char *code) { int i; const unsigned char *bp = buf; unsigned char cur; unsigned char rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7; unsigned char rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15; unsigned char par; par = 0; rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0; rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0; rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0; rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0; for (i = 0; i < 256; i++) { cur = *bp++; par ^= cur; if (i & 0x01) rp1 ^= cur; else rp0 ^= cur; if (i & 0x02) rp3 ^= cur; else rp2 ^= cur; if (i & 0x04) rp5 ^= cur; else rp4 ^= cur; if (i & 0x08) rp7 ^= cur; else rp6 ^= cur; if (i & 0x10) rp9 ^= cur; else rp8 ^= cur; if (i & 0x20) rp11 ^= cur; else rp10 ^= cur; if (i & 0x40) rp13 ^= cur; else rp12 ^= cur; if (i & 0x80) rp15 ^= cur; else rp14 ^= cur; } code[0] = (parity[rp7] << 7) | (parity[rp6] << 6) | (parity[rp5] << 5) | (parity[rp4] << 4) | (parity[rp3] << 3) | (parity[rp2] << 2) | (parity[rp1] << 1) | (parity[rp0]); code[1] = (parity[rp15] << 7) | (parity[rp14] << 6) | (parity[rp13] << 5) | (parity[rp12] << 4) | (parity[rp11] << 3) | (parity[rp10] << 2) | (parity[rp9] << 1) | (parity[rp8]); code[2] = (parity[par & 0xf0] << 7) | (parity[par & 0x0f] << 6) | (parity[par & 0xcc] << 5) | (parity[par & 0x33] << 4) | (parity[par & 0xaa] << 3) | (parity[par & 0x55] << 2); code[0] = ~code[0]; code[1] = ~code[1]; code[2] = ~code[2]; }h]hX* const char parity[256] = { 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 }; void ecc1(const unsigned char *buf, unsigned char *code) { int i; const unsigned char *bp = buf; unsigned char cur; unsigned char rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7; unsigned char rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15; unsigned char par; par = 0; rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0; rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0; rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0; rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0; for (i = 0; i < 256; i++) { cur = *bp++; par ^= cur; if (i & 0x01) rp1 ^= cur; else rp0 ^= cur; if (i & 0x02) rp3 ^= cur; else rp2 ^= cur; if (i & 0x04) rp5 ^= cur; else rp4 ^= cur; if (i & 0x08) rp7 ^= cur; else rp6 ^= cur; if (i & 0x10) rp9 ^= cur; else rp8 ^= cur; if (i & 0x20) rp11 ^= cur; else rp10 ^= cur; if (i & 0x40) rp13 ^= cur; else rp12 ^= cur; if (i & 0x80) rp15 ^= cur; else rp14 ^= cur; } code[0] = (parity[rp7] << 7) | (parity[rp6] << 6) | (parity[rp5] << 5) | (parity[rp4] << 4) | (parity[rp3] << 3) | (parity[rp2] << 2) | (parity[rp1] << 1) | (parity[rp0]); code[1] = (parity[rp15] << 7) | (parity[rp14] << 6) | (parity[rp13] << 5) | (parity[rp12] << 4) | (parity[rp11] << 3) | (parity[rp10] << 2) | (parity[rp9] << 1) | (parity[rp8]); code[2] = (parity[par & 0xf0] << 7) | (parity[par & 0x0f] << 6) | (parity[par & 0xcc] << 5) | (parity[par & 0x33] << 4) | (parity[par & 0xaa] << 3) | (parity[par & 0x55] << 2); code[0] = ~code[0]; code[1] = ~code[1]; code[2] = ~code[2]; }}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhKhjhhubh)}(hStill pretty straightforward. The last three invert statements are there to give a checksum of 0xff 0xff 0xff for an empty flash. In an empty flash all data is 0xff, so the checksum then matches.h]hStill pretty straightforward. The last three invert statements are there to give a checksum of 0xff 0xff 0xff for an empty flash. In an empty flash all data is 0xff, so the checksum then matches.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hI also introduced the parity lookup. I expected this to be the fastest way to calculate the parity, but I will investigate alternatives later on.h]hI also introduced the parity lookup. I expected this to be the fastest way to calculate the parity, but I will investigate alternatives later on.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] attempt-1ah ]h"] attempt 1ah$]h&]uh1hhhhhhhhKubh)}(hhh](h)}(h Analysis 1h]h Analysis 1}(hj hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj hhhhhMubh)}(hThe code works, but is not terribly efficient. On my system it took almost 4 times as much time as the linux driver code. But hey, if it was *that* easy this would have been done long before. No pain. no gain.h](hThe code works, but is not terribly efficient. On my system it took almost 4 times as much time as the linux driver code. But hey, if it was }(hjhhhNhNubhemphasis)}(h*that*h]hthat}(hj%hhhNhNubah}(h]h ]h"]h$]h&]uh1j#hjubh> easy this would have been done long before. No pain. no gain.}(hjhhhNhNubeh}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(h4Fortunately there is plenty of room for improvement.h]h4Fortunately there is plenty of room for improvement.}(hj=hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj hhubh)}(hXIn step 1 we moved from bit-wise calculation to byte-wise calculation. However in C we can also use the unsigned long data type and virtually every modern microprocessor supports 32 bit operations, so why not try to write our code in such a way that we process data in 32 bit chunks.h]hXIn step 1 we moved from bit-wise calculation to byte-wise calculation. However in C we can also use the unsigned long data type and virtually every modern microprocessor supports 32 bit operations, so why not try to write our code in such a way that we process data in 32 bit chunks.}(hjKhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM!hj hhubh)}(hXOf course this means some modification as the row parity is byte by byte. A quick analysis: for the column parity we use the par variable. When extending to 32 bits we can in the end easily calculate rp0 and rp1 from it. (because par now consists of 4 bytes, contributing to rp1, rp0, rp1, rp0 respectively, from MSB to LSB) also rp2 and rp3 can be easily retrieved from par as rp3 covers the first two MSBs and rp2 covers the last two LSBs.h]hXOf course this means some modification as the row parity is byte by byte. A quick analysis: for the column parity we use the par variable. When extending to 32 bits we can in the end easily calculate rp0 and rp1 from it. (because par now consists of 4 bytes, contributing to rp1, rp0, rp1, rp0 respectively, from MSB to LSB) also rp2 and rp3 can be easily retrieved from par as rp3 covers the first two MSBs and rp2 covers the last two LSBs.}(hjYhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM&hj hhubh)}(hX0Note that of course now the loop is executed only 64 times (256/4). And note that care must taken wrt byte ordering. The way bytes are ordered in a long is machine dependent, and might affect us. Anyway, if there is an issue: this code is developed on x86 (to be precise: a DELL PC with a D920 Intel CPU)h]hX0Note that of course now the loop is executed only 64 times (256/4). And note that care must taken wrt byte ordering. The way bytes are ordered in a long is machine dependent, and might affect us. Anyway, if there is an issue: this code is developed on x86 (to be precise: a DELL PC with a D920 Intel CPU)}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM/hj hhubh)}(hAnd of course the performance might depend on alignment, but I expect that the I/O buffers in the nand driver are aligned properly (and otherwise that should be fixed to get maximum performance).h]hAnd of course the performance might depend on alignment, but I expect that the I/O buffers in the nand driver are aligned properly (and otherwise that should be fixed to get maximum performance).}(hjuhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM5hj hhubh)}(hLet's give it a try...h]hLet’s give it a try...}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM9hj hhubeh}(h] analysis-1ah ]h"] analysis 1ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 2h]h Attempt 2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhM=ubjk)}(hX4 extern const char parity[256]; void ecc2(const unsigned char *buf, unsigned char *code) { int i; const unsigned long *bp = (unsigned long *)buf; unsigned long cur; unsigned long rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7; unsigned long rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15; unsigned long par; par = 0; rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0; rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0; rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0; rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0; for (i = 0; i < 64; i++) { cur = *bp++; par ^= cur; if (i & 0x01) rp5 ^= cur; else rp4 ^= cur; if (i & 0x02) rp7 ^= cur; else rp6 ^= cur; if (i & 0x04) rp9 ^= cur; else rp8 ^= cur; if (i & 0x08) rp11 ^= cur; else rp10 ^= cur; if (i & 0x10) rp13 ^= cur; else rp12 ^= cur; if (i & 0x20) rp15 ^= cur; else rp14 ^= cur; } /* we need to adapt the code generation for the fact that rp vars are now long; also the column parity calculation needs to be changed. we'll bring rp4 to 15 back to single byte entities by shifting and xoring */ rp4 ^= (rp4 >> 16); rp4 ^= (rp4 >> 8); rp4 &= 0xff; rp5 ^= (rp5 >> 16); rp5 ^= (rp5 >> 8); rp5 &= 0xff; rp6 ^= (rp6 >> 16); rp6 ^= (rp6 >> 8); rp6 &= 0xff; rp7 ^= (rp7 >> 16); rp7 ^= (rp7 >> 8); rp7 &= 0xff; rp8 ^= (rp8 >> 16); rp8 ^= (rp8 >> 8); rp8 &= 0xff; rp9 ^= (rp9 >> 16); rp9 ^= (rp9 >> 8); rp9 &= 0xff; rp10 ^= (rp10 >> 16); rp10 ^= (rp10 >> 8); rp10 &= 0xff; rp11 ^= (rp11 >> 16); rp11 ^= (rp11 >> 8); rp11 &= 0xff; rp12 ^= (rp12 >> 16); rp12 ^= (rp12 >> 8); rp12 &= 0xff; rp13 ^= (rp13 >> 16); rp13 ^= (rp13 >> 8); rp13 &= 0xff; rp14 ^= (rp14 >> 16); rp14 ^= (rp14 >> 8); rp14 &= 0xff; rp15 ^= (rp15 >> 16); rp15 ^= (rp15 >> 8); rp15 &= 0xff; rp3 = (par >> 16); rp3 ^= (rp3 >> 8); rp3 &= 0xff; rp2 = par & 0xffff; rp2 ^= (rp2 >> 8); rp2 &= 0xff; par ^= (par >> 16); rp1 = (par >> 8); rp1 &= 0xff; rp0 = (par & 0xff); par ^= (par >> 8); par &= 0xff; code[0] = (parity[rp7] << 7) | (parity[rp6] << 6) | (parity[rp5] << 5) | (parity[rp4] << 4) | (parity[rp3] << 3) | (parity[rp2] << 2) | (parity[rp1] << 1) | (parity[rp0]); code[1] = (parity[rp15] << 7) | (parity[rp14] << 6) | (parity[rp13] << 5) | (parity[rp12] << 4) | (parity[rp11] << 3) | (parity[rp10] << 2) | (parity[rp9] << 1) | (parity[rp8]); code[2] = (parity[par & 0xf0] << 7) | (parity[par & 0x0f] << 6) | (parity[par & 0xcc] << 5) | (parity[par & 0x33] << 4) | (parity[par & 0xaa] << 3) | (parity[par & 0x55] << 2); code[0] = ~code[0]; code[1] = ~code[1]; code[2] = ~code[2]; }h]hX4 extern const char parity[256]; void ecc2(const unsigned char *buf, unsigned char *code) { int i; const unsigned long *bp = (unsigned long *)buf; unsigned long cur; unsigned long rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7; unsigned long rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15; unsigned long par; par = 0; rp0 = 0; rp1 = 0; rp2 = 0; rp3 = 0; rp4 = 0; rp5 = 0; rp6 = 0; rp7 = 0; rp8 = 0; rp9 = 0; rp10 = 0; rp11 = 0; rp12 = 0; rp13 = 0; rp14 = 0; rp15 = 0; for (i = 0; i < 64; i++) { cur = *bp++; par ^= cur; if (i & 0x01) rp5 ^= cur; else rp4 ^= cur; if (i & 0x02) rp7 ^= cur; else rp6 ^= cur; if (i & 0x04) rp9 ^= cur; else rp8 ^= cur; if (i & 0x08) rp11 ^= cur; else rp10 ^= cur; if (i & 0x10) rp13 ^= cur; else rp12 ^= cur; if (i & 0x20) rp15 ^= cur; else rp14 ^= cur; } /* we need to adapt the code generation for the fact that rp vars are now long; also the column parity calculation needs to be changed. we'll bring rp4 to 15 back to single byte entities by shifting and xoring */ rp4 ^= (rp4 >> 16); rp4 ^= (rp4 >> 8); rp4 &= 0xff; rp5 ^= (rp5 >> 16); rp5 ^= (rp5 >> 8); rp5 &= 0xff; rp6 ^= (rp6 >> 16); rp6 ^= (rp6 >> 8); rp6 &= 0xff; rp7 ^= (rp7 >> 16); rp7 ^= (rp7 >> 8); rp7 &= 0xff; rp8 ^= (rp8 >> 16); rp8 ^= (rp8 >> 8); rp8 &= 0xff; rp9 ^= (rp9 >> 16); rp9 ^= (rp9 >> 8); rp9 &= 0xff; rp10 ^= (rp10 >> 16); rp10 ^= (rp10 >> 8); rp10 &= 0xff; rp11 ^= (rp11 >> 16); rp11 ^= (rp11 >> 8); rp11 &= 0xff; rp12 ^= (rp12 >> 16); rp12 ^= (rp12 >> 8); rp12 &= 0xff; rp13 ^= (rp13 >> 16); rp13 ^= (rp13 >> 8); rp13 &= 0xff; rp14 ^= (rp14 >> 16); rp14 ^= (rp14 >> 8); rp14 &= 0xff; rp15 ^= (rp15 >> 16); rp15 ^= (rp15 >> 8); rp15 &= 0xff; rp3 = (par >> 16); rp3 ^= (rp3 >> 8); rp3 &= 0xff; rp2 = par & 0xffff; rp2 ^= (rp2 >> 8); rp2 &= 0xff; par ^= (par >> 16); rp1 = (par >> 8); rp1 &= 0xff; rp0 = (par & 0xff); par ^= (par >> 8); par &= 0xff; code[0] = (parity[rp7] << 7) | (parity[rp6] << 6) | (parity[rp5] << 5) | (parity[rp4] << 4) | (parity[rp3] << 3) | (parity[rp2] << 2) | (parity[rp1] << 1) | (parity[rp0]); code[1] = (parity[rp15] << 7) | (parity[rp14] << 6) | (parity[rp13] << 5) | (parity[rp12] << 4) | (parity[rp11] << 3) | (parity[rp10] << 2) | (parity[rp9] << 1) | (parity[rp8]); code[2] = (parity[par & 0xf0] << 7) | (parity[par & 0x0f] << 6) | (parity[par & 0xcc] << 5) | (parity[par & 0x33] << 4) | (parity[par & 0xaa] << 3) | (parity[par & 0x55] << 2); code[0] = ~code[0]; code[1] = ~code[1]; code[2] = ~code[2]; }}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMAhjhhubh)}(hX The parity array is not shown any more. Note also that for these examples I kinda deviated from my regular programming style by allowing multiple statements on a line, not using { } in then and else blocks with only a single statement and by using operators like ^=h]hX The parity array is not shown any more. Note also that for these examples I kinda deviated from my regular programming style by allowing multiple statements on a line, not using { } in then and else blocks with only a single statement and by using operators like ^=}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] attempt-2ah ]h"] attempt 2ah$]h&]uh1hhhhhhhhM=ubh)}(hhh](h)}(h Analysis 2h]h Analysis 2}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hXcThe code (of course) works, and hurray: we are a little bit faster than the linux driver code (about 15%). But wait, don't cheer too quickly. There is more to be gained. If we look at e.g. rp14 and rp15 we see that we either xor our data with rp14 or with rp15. However we also have par which goes over all data. This means there is no need to calculate rp14 as it can be calculated from rp15 through rp14 = par ^ rp15, because par = rp14 ^ rp15; (or if desired we can avoid calculating rp15 and calculate it from rp14). That is why some places refer to inverse parity. Of course the same thing holds for rp4/5, rp6/7, rp8/9, rp10/11 and rp12/13. Effectively this means we can eliminate the else clause from the if statements. Also we can optimise the calculation in the end a little bit by going from long to byte first. Actually we can even avoid the table lookupsЊh]hXeThe code (of course) works, and hurray: we are a little bit faster than the linux driver code (about 15%). But wait, don’t cheer too quickly. There is more to be gained. If we look at e.g. rp14 and rp15 we see that we either xor our data with rp14 or with rp15. However we also have par which goes over all data. This means there is no need to calculate rp14 as it can be calculated from rp15 through rp14 = par ^ rp15, because par = rp14 ^ rp15; (or if desired we can avoid calculating rp15 and calculate it from rp14). That is why some places refer to inverse parity. Of course the same thing holds for rp4/5, rp6/7, rp8/9, rp10/11 and rp12/13. Effectively this means we can eliminate the else clause from the if statements. Also we can optimise the calculation in the end a little bit by going from long to byte first. Actually we can even avoid the table lookups}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] analysis-2ah ]h"] analysis 2ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 3h]h Attempt 3}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hOdd replaced::h]h Odd replaced:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubjk)}(hXif (i & 0x01) rp5 ^= cur; else rp4 ^= cur; if (i & 0x02) rp7 ^= cur; else rp6 ^= cur; if (i & 0x04) rp9 ^= cur; else rp8 ^= cur; if (i & 0x08) rp11 ^= cur; else rp10 ^= cur; if (i & 0x10) rp13 ^= cur; else rp12 ^= cur; if (i & 0x20) rp15 ^= cur; else rp14 ^= cur;h]hXif (i & 0x01) rp5 ^= cur; else rp4 ^= cur; if (i & 0x02) rp7 ^= cur; else rp6 ^= cur; if (i & 0x04) rp9 ^= cur; else rp8 ^= cur; if (i & 0x08) rp11 ^= cur; else rp10 ^= cur; if (i & 0x10) rp13 ^= cur; else rp12 ^= cur; if (i & 0x20) rp15 ^= cur; else rp14 ^= cur;}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjhhubh)}(hwith::h]hwith:}(hj"hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubjk)}(hif (i & 0x01) rp5 ^= cur; if (i & 0x02) rp7 ^= cur; if (i & 0x04) rp9 ^= cur; if (i & 0x08) rp11 ^= cur; if (i & 0x10) rp13 ^= cur; if (i & 0x20) rp15 ^= cur;h]hif (i & 0x01) rp5 ^= cur; if (i & 0x02) rp7 ^= cur; if (i & 0x04) rp9 ^= cur; if (i & 0x08) rp11 ^= cur; if (i & 0x10) rp13 ^= cur; if (i & 0x20) rp15 ^= cur;}hj0sbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjhhubh)}(hand outside the loop added::h]hand outside the loop added:}(hj>hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubjk)}(hqrp4 = par ^ rp5; rp6 = par ^ rp7; rp8 = par ^ rp9; rp10 = par ^ rp11; rp12 = par ^ rp13; rp14 = par ^ rp15;h]hqrp4 = par ^ rp5; rp6 = par ^ rp7; rp8 = par ^ rp9; rp10 = par ^ rp11; rp12 = par ^ rp13; rp14 = par ^ rp15;}hjLsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjhhubh)}(hAnd after that the code takes about 30% more time, although the number of statements is reduced. This is also reflected in the assembly code.h]hAnd after that the code takes about 30% more time, although the number of statements is reduced. This is also reflected in the assembly code.}(hjZhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] attempt-3ah ]h"] attempt 3ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Analysis 3h]h Analysis 3}(hjshhhNhNubah}(h]h ]h"]h$]h&]uh1hhjphhhhhMubh)}(hXVery weird. Guess it has to do with caching or instruction parallelism or so. I also tried on an eeePC (Celeron, clocked at 900 Mhz). Interesting observation was that this one is only 30% slower (according to time) executing the code as my 3Ghz D920 processor.h]hXVery weird. Guess it has to do with caching or instruction parallelism or so. I also tried on an eeePC (Celeron, clocked at 900 Mhz). Interesting observation was that this one is only 30% slower (according to time) executing the code as my 3Ghz D920 processor.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjphhubh)}(hWell, it was expected not to be easy so maybe instead move to a different track: let's move back to the code from attempt2 and do some loop unrolling. This will eliminate a few if statements. I'll try different amounts of unrolling to see what works best.h]hXWell, it was expected not to be easy so maybe instead move to a different track: let’s move back to the code from attempt2 and do some loop unrolling. This will eliminate a few if statements. I’ll try different amounts of unrolling to see what works best.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjphhubeh}(h] analysis-3ah ]h"] analysis 3ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 4h]h Attempt 4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hCUnrolled the loop 1, 2, 3 and 4 times. For 4 the code starts with::h]hBUnrolled the loop 1, 2, 3 and 4 times. For 4 the code starts with:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubjk)}(hX$for (i = 0; i < 4; i++) { cur = *bp++; par ^= cur; rp4 ^= cur; rp6 ^= cur; rp8 ^= cur; rp10 ^= cur; if (i & 0x1) rp13 ^= cur; else rp12 ^= cur; if (i & 0x2) rp15 ^= cur; else rp14 ^= cur; cur = *bp++; par ^= cur; rp5 ^= cur; rp6 ^= cur; ...h]hX$for (i = 0; i < 4; i++) { cur = *bp++; par ^= cur; rp4 ^= cur; rp6 ^= cur; rp8 ^= cur; rp10 ^= cur; if (i & 0x1) rp13 ^= cur; else rp12 ^= cur; if (i & 0x2) rp15 ^= cur; else rp14 ^= cur; cur = *bp++; par ^= cur; rp5 ^= cur; rp6 ^= cur; ...}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjhhubeh}(h] attempt-4ah ]h"] attempt 4ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Analysis 4h]h Analysis 4}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hUnrolling once gains about 15%h]hUnrolling once gains about 15%}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(h+Unrolling twice keeps the gain at about 15%h]h+Unrolling twice keeps the gain at about 15%}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(h@Unrolling three times gives a gain of 30% compared to attempt 2.h]h@Unrolling three times gives a gain of 30% compared to attempt 2.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hTUnrolling four times gives a marginal improvement compared to unrolling three times.h]hTUnrolling four times gives a marginal improvement compared to unrolling three times.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hI decided to proceed with a four time unrolled loop anyway. It was my gut feeling that in the next steps I would obtain additional gain from it.h]hI decided to proceed with a four time unrolled loop anyway. It was my gut feeling that in the next steps I would obtain additional gain from it.}(hj#hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hXThe next step was triggered by the fact that par contains the xor of all bytes and rp4 and rp5 each contain the xor of half of the bytes. So in effect par = rp4 ^ rp5. But as xor is commutative we can also say that rp5 = par ^ rp4. So no need to keep both rp4 and rp5 around. We can eliminate rp5 (or rp4, but I already foresaw another optimisation). The same holds for rp6/7, rp8/9, rp10/11 rp12/13 and rp14/15.h]hXThe next step was triggered by the fact that par contains the xor of all bytes and rp4 and rp5 each contain the xor of half of the bytes. So in effect par = rp4 ^ rp5. But as xor is commutative we can also say that rp5 = par ^ rp4. So no need to keep both rp4 and rp5 around. We can eliminate rp5 (or rp4, but I already foresaw another optimisation). The same holds for rp6/7, rp8/9, rp10/11 rp12/13 and rp14/15.}(hj1hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] analysis-4ah ]h"] analysis 4ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 5h]h Attempt 5}(hjJhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjGhhhhhM ubh)}(hEffectively so all odd digit rp assignments in the loop were removed. This included the else clause of the if statements. Of course after the loop we need to correct things by adding code like::h]hEffectively so all odd digit rp assignments in the loop were removed. This included the else clause of the if statements. Of course after the loop we need to correct things by adding code like:}(hjXhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM hjGhhubjk)}(hrp5 = par ^ rp4;h]hrp5 = par ^ rp4;}hjfsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjGhhubh)}(h|Also the initial assignments (rp5 = 0; etc) could be removed. Along the line I also removed the initialisation of rp0/1/2/3.h]h|Also the initial assignments (rp5 = 0; etc) could be removed. Along the line I also removed the initialisation of rp0/1/2/3.}(hjthhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjGhhubeh}(h] attempt-5ah ]h"] attempt 5ah$]h&]uh1hhhhhhhhM ubh)}(hhh](h)}(h Analysis 5h]h Analysis 5}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hMeasurements showed this was a good move. The run-time roughly halved compared with attempt 4 with 4 times unrolled, and we only require 1/3rd of the processor time compared to the current code in the linux kernel.h]hMeasurements showed this was a good move. The run-time roughly halved compared with attempt 4 with 4 times unrolled, and we only require 1/3rd of the processor time compared to the current code in the linux kernel.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hHowever, still I thought there was more. I didn't like all the if statements. Why not keep a running parity and only keep the last if statement. Time for yet another version!h]hHowever, still I thought there was more. I didn’t like all the if statements. Why not keep a running parity and only keep the last if statement. Time for yet another version!}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] analysis-5ah ]h"] analysis 5ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 6h]h Attempt 6}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhM$ubh)}(h-THe code within the for loop was changed to::h]h,THe code within the for loop was changed to:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM&hjhhubjk)}(hXfor (i = 0; i < 4; i++) { cur = *bp++; tmppar = cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp8 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp10 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; par ^= tmppar; if ((i & 0x1) == 0) rp12 ^= tmppar; if ((i & 0x2) == 0) rp14 ^= tmppar; }h]hXfor (i = 0; i < 4; i++) { cur = *bp++; tmppar = cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp8 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp10 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp8 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; par ^= tmppar; if ((i & 0x1) == 0) rp12 ^= tmppar; if ((i & 0x2) == 0) rp14 ^= tmppar; }}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhM(hjhhubh)}(hAs you can see tmppar is used to accumulate the parity within a for iteration. In the last 3 statements is added to par and, if needed, to rp12 and rp14.h]hAs you can see tmppar is used to accumulate the parity within a for iteration. In the last 3 statements is added to par and, if needed, to rp12 and rp14.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMChjhhubh)}(hXWhile making the changes I also found that I could exploit that tmppar contains the running parity for this iteration. So instead of having: rp4 ^= cur; rp6 ^= cur; I removed the rp6 ^= cur; statement and did rp6 ^= tmppar; on next statement. A similar change was done for rp8 and rp10h]hXWhile making the changes I also found that I could exploit that tmppar contains the running parity for this iteration. So instead of having: rp4 ^= cur; rp6 ^= cur; I removed the rp6 ^= cur; statement and did rp6 ^= tmppar; on next statement. A similar change was done for rp8 and rp10}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMGhjhhubeh}(h] attempt-6ah ]h"] attempt 6ah$]h&]uh1hhhhhhhhM$ubh)}(hhh](h)}(h Analysis 6h]h Analysis 6}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMOubh)}(hX}Measuring this code again showed big gain. When executing the original linux code 1 million times, this took about 1 second on my system. (using time to measure the performance). After this iteration I was back to 0.075 sec. Actually I had to decide to start measuring over 10 million iterations in order not to lose too much accuracy. This one definitely seemed to be the jackpot!h]hX}Measuring this code again showed big gain. When executing the original linux code 1 million times, this took about 1 second on my system. (using time to measure the performance). After this iteration I was back to 0.075 sec. Actually I had to decide to start measuring over 10 million iterations in order not to lose too much accuracy. This one definitely seemed to be the jackpot!}(hj!hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMQhjhhubh)}(h`There is a little bit more room for improvement though. There are three places with statements::h]h_There is a little bit more room for improvement though. There are three places with statements:}(hj/hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMXhjhhubjk)}(hrp4 ^= cur; rp6 ^= cur;h]hrp4 ^= cur; rp6 ^= cur;}hj=sbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhM[hjhhubh)}(hIt seems more efficient to also maintain a variable rp4_6 in the while loop; This eliminates 3 statements per loop. Of course after the loop we need to correct by adding::h]hIt seems more efficient to also maintain a variable rp4_6 in the while loop; This eliminates 3 statements per loop. Of course after the loop we need to correct by adding:}(hjKhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhM]hjhhubjk)}(hrp4 ^= rp4_6; rp6 ^= rp4_6h]hrp4 ^= rp4_6; rp6 ^= rp4_6}hjYsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMahjhhubh)}(hX2Furthermore there are 4 sequential assignments to rp8. This can be encoded slightly more efficiently by saving tmppar before those 4 lines and later do rp8 = rp8 ^ tmppar ^ notrp8; (where notrp8 is the value of rp8 before those 4 lines). Again a use of the commutative property of xor. Time for a new test!h]hX2Furthermore there are 4 sequential assignments to rp8. This can be encoded slightly more efficiently by saving tmppar before those 4 lines and later do rp8 = rp8 ^ tmppar ^ notrp8; (where notrp8 is the value of rp8 before those 4 lines). Again a use of the commutative property of xor. Time for a new test!}(hjghhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMdhjhhubeh}(h] analysis-6ah ]h"] analysis 6ah$]h&]uh1hhhhhhhhMOubh)}(hhh](h)}(h Attempt 7h]h Attempt 7}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhj}hhhhhMmubh)}(hThe new code now looks like::h]hThe new code now looks like:}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMohj}hhubjk)}(hXfor (i = 0; i < 4; i++) { cur = *bp++; tmppar = cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp8 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp10 ^= tmppar; notrp8 = tmppar; cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp8 = rp8 ^ tmppar ^ notrp8; cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; par ^= tmppar; if ((i & 0x1) == 0) rp12 ^= tmppar; if ((i & 0x2) == 0) rp14 ^= tmppar; } rp4 ^= rp4_6; rp6 ^= rp4_6;h]hXfor (i = 0; i < 4; i++) { cur = *bp++; tmppar = cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp8 ^= tmppar; cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp10 ^= tmppar; notrp8 = tmppar; cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; rp8 = rp8 ^ tmppar ^ notrp8; cur = *bp++; tmppar ^= cur; rp4_6 ^= cur; cur = *bp++; tmppar ^= cur; rp6 ^= cur; cur = *bp++; tmppar ^= cur; rp4 ^= cur; cur = *bp++; tmppar ^= cur; par ^= tmppar; if ((i & 0x1) == 0) rp12 ^= tmppar; if ((i & 0x2) == 0) rp14 ^= tmppar; } rp4 ^= rp4_6; rp6 ^= rp4_6;}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMqhj}hhubh)}(h,Not a big change, but every penny counts :-)h]h,Not a big change, but every penny counts :-)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj}hhubeh}(h] attempt-7ah ]h"] attempt 7ah$]h&]uh1hhhhhhhhMmubh)}(hhh](h)}(h Analysis 7h]h Analysis 7}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hActually this made things worse. Not very much, but I don't want to move into the wrong direction. Maybe something to investigate later. Could have to do with caching again.h]hActually this made things worse. Not very much, but I don’t want to move into the wrong direction. Maybe something to investigate later. Could have to do with caching again.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hGuess that is what there is to win within the loop. Maybe unrolling one more time will help. I'll keep the optimisations from 7 for now.h]hGuess that is what there is to win within the loop. Maybe unrolling one more time will help. I’ll keep the optimisations from 7 for now.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] analysis-7ah ]h"] analysis 7ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 8h]h Attempt 8}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(h Unrolled the loop one more time.h]h Unrolled the loop one more time.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] attempt-8ah ]h"] attempt 8ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Analysis 8h]h Analysis 8}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hXIThis makes things worse. Let's stick with attempt 6 and continue from there. Although it seems that the code within the loop cannot be optimised further there is still room to optimize the generation of the ecc codes. We can simply calculate the total parity. If this is 0 then rp4 = rp5 etc. If the parity is 1, then rp4 = !rp5;h]hXKThis makes things worse. Let’s stick with attempt 6 and continue from there. Although it seems that the code within the loop cannot be optimised further there is still room to optimize the generation of the ecc codes. We can simply calculate the total parity. If this is 0 then rp4 = rp5 etc. If the parity is 1, then rp4 = !rp5;}(hj-hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hxBut if rp4 = rp5 we do not need rp5 etc. We can just write the even bits in the result byte and then do something like::h]hwBut if rp4 = rp5 we do not need rp5 etc. We can just write the even bits in the result byte and then do something like:}(hj;hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubjk)}(hcode[0] |= (code[0] << 1);h]hcode[0] |= (code[0] << 1);}hjIsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjhhubh)}(hLets test this.h]hLets test this.}(hjWhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h] analysis-8ah ]h"] analysis 8ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Attempt 9h]h Attempt 9}(hjphhhNhNubah}(h]h ]h"]h$]h&]uh1hhjmhhhhhMubh)}(hXChanged the code but again this slightly degrades performance. Tried all kind of other things, like having dedicated parity arrays to avoid the shift after parity[rp7] << 7; No gain. Change the lookup using the parity array by using shift operators (e.g. replace parity[rp7] << 7 with::h]hXChanged the code but again this slightly degrades performance. Tried all kind of other things, like having dedicated parity arrays to avoid the shift after parity[rp7] << 7; No gain. Change the lookup using the parity array by using shift operators (e.g. replace parity[rp7] << 7 with:}(hj~hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjmhhubjk)}(hErp7 ^= (rp7 << 4); rp7 ^= (rp7 << 2); rp7 ^= (rp7 << 1); rp7 &= 0x80;h]hErp7 ^= (rp7 << 4); rp7 ^= (rp7 << 2); rp7 ^= (rp7 << 1); rp7 &= 0x80;}hjsbah}(h]h ]h"]h$]h&]jzj{uh1jjhhhMhjmhhubh)}(hNo gain.h]hNo gain.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjmhhubh)}(hjThe only marginal change was inverting the parity bits, so we can remove the last three invert statements.h]hjThe only marginal change was inverting the parity bits, so we can remove the last three invert statements.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjmhhubh)}(hX|Ah well, pity this does not deliver more. Then again 10 million iterations using the linux driver code takes between 13 and 13.5 seconds, whereas my code now takes about 0.73 seconds for those 10 million iterations. So basically I've improved the performance by a factor 18 on my system. Not that bad. Of course on different hardware you will get different results. No warranties!h]hX~Ah well, pity this does not deliver more. Then again 10 million iterations using the linux driver code takes between 13 and 13.5 seconds, whereas my code now takes about 0.73 seconds for those 10 million iterations. So basically I’ve improved the performance by a factor 18 on my system. Not that bad. Of course on different hardware you will get different results. No warranties!}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjmhhubh)}(hBut of course there is no such thing as a free lunch. The codesize almost tripled (from 562 bytes to 1434 bytes). Then again, it is not that much.h]hBut of course there is no such thing as a free lunch. The codesize almost tripled (from 562 bytes to 1434 bytes). Then again, it is not that much.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjmhhubeh}(h] attempt-9ah ]h"] attempt 9ah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(hCorrecting errorsh]hCorrecting errors}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjhhhhhMubh)}(hpFor correcting errors I again used the ST application note as a starter, but I also peeked at the existing code.h]hpFor correcting errors I again used the ST application note as a starter, but I also peeked at the existing code.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hThe algorithm itself is pretty straightforward. Just xor the given and the calculated ecc. If all bytes are 0 there is no problem. If 11 bits are 1 we have one correctable bit error. If there is 1 bit 1, we have an error in the given ecc code.h]hThe algorithm itself is pretty straightforward. Just xor the given and the calculated ecc. If all bytes are 0 there is no problem. If 11 bits are 1 we have one correctable bit error. If there is 1 bit 1, we have an error in the given ecc code.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hIt proved to be fastest to do some table lookups. Performance gain introduced by this is about a factor 2 on my system when a repair had to be done, and 1% or so if no repair had to be done.h]hIt proved to be fastest to do some table lookups. Performance gain introduced by this is about a factor 2 on my system when a repair had to be done, and 1% or so if no repair had to be done.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubh)}(hQCode size increased from 330 bytes to 686 bytes for this function. (gcc 4.2, -O3)h]hQCode size increased from 330 bytes to 686 bytes for this function. (gcc 4.2, -O3)}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhjhhubeh}(h]correcting-errorsah ]h"]correcting errorsah$]h&]uh1hhhhhhhhMubh)}(hhh](h)}(h Conclusionh]h Conclusion}(hj.hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj+hhhhhMubh)}(hThe gain when calculating the ecc is tremendous. Om my development hardware a speedup of a factor of 18 for ecc calculation was achieved. On a test on an embedded system with a MIPS core a factor 7 was obtained.h]hThe gain when calculating the ecc is tremendous. Om my development hardware a speedup of a factor of 18 for ecc calculation was achieved. On a test on an embedded system with a MIPS core a factor 7 was obtained.}(hj<hhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubh)}(hoOn a test with a Linksys NSLU2 (ARMv5TE processor) the speedup was a factor 5 (big endian mode, gcc 4.1.2, -O3)h]hoOn a test with a Linksys NSLU2 (ARMv5TE processor) the speedup was a factor 5 (big endian mode, gcc 4.1.2, -O3)}(hjJhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubh)}(h~For correction not much gain could be obtained (as bitflips are rare). Then again there are also much less cycles spent there.h]h~For correction not much gain could be obtained (as bitflips are rare). Then again there are also much less cycles spent there.}(hjXhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubh)}(hXIt seems there is not much more gain possible in this, at least when programmed in C. Of course it might be possible to squeeze something more out of it with an assembler program, but due to pipeline behaviour etc this is very tricky (at least for intel hw).h]hXIt seems there is not much more gain possible in this, at least when programmed in C. Of course it might be possible to squeeze something more out of it with an assembler program, but due to pipeline behaviour etc this is very tricky (at least for intel hw).}(hjfhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubh)}(hAuthor: Frans Meulenbroeksh]hAuthor: Frans Meulenbroeks}(hjthhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubh)}(h6Copyright (C) 2008 Koninklijke Philips Electronics NV.h]h6Copyright (C) 2008 Koninklijke Philips Electronics NV.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhhhMhj+hhubeh}(h] conclusionah ]h"] conclusionah$]h&]uh1hhhhhhhhMubeh}(h]nand-error-correction-codeah ]h"]nand error-correction codeah$]h&]uh1hhhhhhhhKubeh}(h]h ]h"]h$]h&]sourcehuh1hcurrent_sourceN current_lineNsettingsdocutils.frontendValues)}(hN generatorN datestampN source_linkN source_urlN toc_backlinksjfootnote_backlinksK sectnum_xformKstrip_commentsNstrip_elements_with_classesN strip_classesN report_levelK halt_levelKexit_status_levelKdebugNwarning_streamN tracebackinput_encoding utf-8-siginput_encoding_error_handlerstrictoutput_encodingutf-8output_encoding_error_handlerjerror_encodingutf-8error_encoding_error_handlerbackslashreplace language_codeenrecord_dependenciesNconfigN id_prefixhauto_id_prefixid dump_settingsNdump_internalsNdump_transformsNdump_pseudo_xmlNexpose_internalsNstrict_visitorN_disable_configN_sourcehʌ _destinationN _config_files]7/var/lib/git/docbuild/linux/Documentation/docutils.confafile_insertion_enabled raw_enabledKline_length_limitM'pep_referencesN pep_base_urlhttps://peps.python.org/pep_file_url_templatepep-%04drfc_referencesN rfc_base_url&https://datatracker.ietf.org/doc/html/ tab_widthKtrim_footnote_reference_spacesyntax_highlightlong smart_quotessmartquotes_locales]character_level_inline_markupdoctitle_xform docinfo_xformKsectsubtitle_xform image_loadinglinkembed_stylesheetcloak_email_addressessection_self_linkenvNubreporterNindirect_targets]substitution_defs}substitution_names}refnames}refids}nameids}(jjhhjHjEjj~jjjjjjjjjjjmjjjjjjjDjAjjjjj j jzjwjjjjjjjjjgjjj(j%jju nametypes}(jhjHjjjjjjjmjjjDjjj jzjjjjjjj(juh}(jhhhjEjj~jKjjjjjj jjjjjjjjjpjjjAjjjGjjj jjwjjj}jjjjjgjjjmj%jjj+u footnote_refs} citation_refs} autofootnotes]autofootnote_refs]symbol_footnotes]symbol_footnote_refs] footnotes] citations]autofootnote_startKsymbol_footnote_startK id_counter collectionsCounter}Rparse_messages](hsystem_message)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hj)hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj&ubah}(h]h ]h"]h$]h&]levelKtypeINFOlineK.sourcehuh1j$hjubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hjEhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjBubah}(h]h ]h"]h$]h&]levelKtypej?lineK/sourcehuh1j$hjNubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hj`hhhNhNubah}(h]h ]h"]h$]h&]uh1hhj]ubah}(h]h ]h"]h$]h&]levelKtypej?lineK0sourcehuh1j$hjubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hj{hhhNhNubah}(h]h ]h"]h$]h&]uh1hhjxubah}(h]h ]h"]h$]h&]levelKtypej?lineK1sourcehuh1j$hjubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej?lineK2sourcehuh1j$hj/ubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej?lineK3sourcehuh1j$hjfubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej?lineK4sourcehuh1j$hj ubj%)}(hhh]h)}(heUnexpected possible title overline or transition. Treating it as ordinary text because it's so short.h]hgUnexpected possible title overline or transition. Treating it as ordinary text because it’s so short.}(hjhhhNhNubah}(h]h ]h"]h$]h&]uh1hhjubah}(h]h ]h"]h$]h&]levelKtypej?lineK5sourcehuh1j$hjZ ubetransform_messages] transformerN include_log] decorationNhhub.