Earlier we developed TriMedia code to dump the contents of the NAND flash device on the 2Wire boards. [1]
The diagram below illustrates the organisation of a NAND flash memory array. In addition to a main data page area (usually 512 bytes), NAND devices also have a small ‘Spare Area’ of extra bytes per flash page. In small NAND arrays, this ‘Spare Area’ typically holds 16 bytes.
NAND Memory Array Organisation
This is what that NAND flash Spare Area looks like in a 2Wire 2701HGV:
$ xxd -g4 2701HGV-C_6.3.9.41_nand_full_oob_dump_2.img | cut -c10-44 | ./parsehex
[...]
0199200: c0cf 3c55 24ff 69a5 00ff ff96 0600 ff99 ..<U$.i.........
0199400: 003f fcc0 24ff cc30 00ff ff96 0600 ff99 .?..$..0........
0199600: c3cc 0c3f 24ff c0c0 00ff ff96 0600 ff99 ...?$...........
0199800: a699 693f 24ff cf3c 00ff ff96 0600 ff99 ..i?$..<........
0199a00: 0030 0cfc 24ff c33c 00ff ff96 0600 ff99 .0..$..<........
[...]
The NAND Spare Area is also known as the redundancy area or the out-of-band (OOB) area of the flash page. Manufacturers use the area to store bad block information, to hold mapping data for the flash translation layer, and to store Error Correction Code (ECC)
The NAND spare area of the 2Wire 2701HGV router was found to include the check bits of ECC.
The ECC scheme used by 2Wire is based on a Hamming Code algorithm.
In a Hamming Code algorithm, the NAND page (aka the data block) is divided into various partitions – halves, quarters, eighths, even and odd rows and columns, and so on. Parity bits are calculated for each partition of the data block. These become the ECC bits.
The Hamming scheme allows an individual bit in error to be identified and corrected. The scheme can also detect (but not correct) a second errored bit in the same data block.
In 2Wire‘s modified Hamming Code algorithm, a data block of 256 bytes is used. This is half the size of a small NAND flash page (512 bytes). 22-bits are used for calculating the various row and column ECC parities for each 256 byte block. However, in 2Wire’s modified scheme, an additional check bit is used for the column parity ECC byte for each of those blocks. This means that for every 256 byte data block, the scheme uses 23 bits to hold all of the ECC parity bits. Three bytes are needed to store those 23 bits, leaving, it seems, one bit of those three bytes unused.
The 2Wire configuration of ECC requires in total six bytes from the out-of-band area for every 512 byte NAND page.
We examined ECC algorithms from NetBSD/Atmel, Numonyx/Micron and from Frans Meulenbroeks of Philips NV. However, no algorithm worked ‘out of the box’. Because of that extra bit for overall column parity, the ECC scheme used by 2Wire is slightly different to anything we could find published. Instead, the existing ECC algorithms for calculation, detection and correction were slightly tweaked.
It was Meulenbroeks‘ code which we selected for tweaking, because of its simplicity and its elegance.[2] Meulenbroeks uses this code as his foundation for discussing the speed optimisations of ECC algorithms. However, we chose to use his unoptimised algorithm because it is so easy to follow. And on a quad core AMD64 it’s not that slow either. The code takes a fraction of a second to calculate the ECCs for all the sectors in a 32MByte NAND image.
// Modified from Linux kernel docs.. asbokid 2012
// GPL v.3
// Author: Frans Meulenbroeks
// Copyright (C) 2008 Koninklijke Philips Electronics NV.
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 meul_ecc1_2wire(const unsigned char *buf, unsigned char *code)
{
int i;
const unsigned char *bp = buf;
unsigned char cur, par;
unsigned char rp0, rp1, rp2, rp3, rp4, rp5, rp6, rp7;
unsigned char rp8, rp9, rp10, rp11, rp12, rp13, rp14, rp15;
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) |
(parity[par & 0x00] << 1) |
(parity[par & 0xff]); // asbokid added for 2wire
/* code[0] = ~code[0];
code[1] = ~code[1]; // asbokid removed for 2wire
code[2] = ~code[2]; */
}
In tests the algorithm works fine on the 2Wire NAND contents. It correctly calculates the ECC for each data block and checks it against the stored ECC code in the out-of-band area of the NAND:
$ gcc -o nanddumpparse nanddumpparse.c 2wire_ecc.c
$ ./nanddumpparse
Usage: ./nanddumpparse nandimage.bin nandimage.oob
$ ./nanddumpparse 2701HGV-C_6.3.9.41_nand_full_dump_2.img 2701HGV-C_6.3.9.41_nand_full_oob_dump_2.img
Read 33554432 bytes of NAND data from 2701HGV-C_6.3.9.41_nand_full_dump_2.img
Read 1048576 bytes of NAND OOB from 2701HGV-C_6.3.9.41_nand_full_oob_dump_2.img
[...]
Offset 0030000 - [bytes 000-255] : ECC1(stored) = c3:30:0c; ECC1(calc) = c3:30:0c; ECC okay
Offset 0030100 - [bytes 256-511] : ECC2(stored) = 95:56:65; ECC2(calc) = 95:56:65; ECC okay
Offset 0030200 - [bytes 000-255] : ECC1(stored) = fc:fc:f0; ECC1(calc) = fc:fc:f0; ECC okay
Offset 0030300 - [bytes 256-511] : ECC2(stored) = a6:59:95; ECC2(calc) = a6:59:95; ECC okay
Offset 0030400 - [bytes 000-255] : ECC1(stored) = 30:f0:3c; ECC1(calc) = 30:f0:3c; ECC okay
Offset 0030500 - [bytes 256-511] : ECC2(stored) = fc:0f:00; ECC2(calc) = fc:0f:00; ECC okay
Offset 0030600 - [bytes 000-255] : ECC1(stored) = 96:a9:55; ECC1(calc) = 96:a9:55; ECC okay
Offset 0030700 - [bytes 256-511] : ECC2(stored) = a5:a6:65; ECC2(calc) = a5:a6:65; ECC okay
Offset 0030800 - [bytes 000-255] : ECC1(stored) = 66:56:69; ECC1(calc) = 66:56:69; ECC okay
Offset 0030900 - [bytes 256-511] : ECC2(stored) = f0:0f:fc; ECC2(calc) = f0:0f:fc; ECC okay
Offset 0030a00 - [bytes 000-255] : ECC1(stored) = 99:56:69; ECC1(calc) = 99:56:69; ECC okay
Offset 0030b00 - [bytes 256-511] : ECC2(stored) = 5a:56:59; ECC2(calc) = 5a:56:59; ECC okay
Offset 0030c00 - [bytes 000-255] : ECC1(stored) = 3c:3f:00; ECC1(calc) = 3c:3f:00; ECC okay
Offset 0030d00 - [bytes 256-511] : ECC2(stored) = 95:56:65; ECC2(calc) = 95:56:65; ECC okay
Offset 0030e00 - [bytes 000-255] : ECC1(stored) = 65:69:95; ECC1(calc) = 65:69:95; ECC okay
[...]
Offset 1ffbd00 - [bytes 256-511] : ECC2(stored) = 30:f0:30; ECC2(calc) = 30:f0:30; ECC okay
Offset 1ffbe00 - [bytes 000-255] : ECC1(stored) = 6a:66:65; ECC1(calc) = 6a:66:65; ECC okay
Offset 1ffbf00 - [bytes 256-511] : ECC2(stored) = 9a:66:95; ECC2(calc) = 9a:66:95; ECC okay
ECC Errors: CORRECTABLE 0; UNCORRECTABLE 0
Page Utilisation: USED 30199; FREED 2979, ERASED 32347; TOTAL 65536
$
The ECC code patched for 2Wire flash contents can be downloaded from [3].
The 16-byte Spare Area is also safeguarded against corruption. This is achieved through a simple modulo-256 checksum which is performed on bytes [8:14] of the Spare Area.
Using the Spare Area excerpt below, the mod-256 checksum is (0×00+0xff+0xff+0×96+0×06+0×00+0xff) % 0×100 = 0×99, which is then stored in byte 15 of the Spare Area.
$ xxd -g4 2701HGV-C_6.3.9.41_nand_full_oob_dump_2.img | cut -c10-44 | ./parsehex
[...]
0199200: c0cf 3c55 24ff 69a5 00ff ff96 0600 ff99 ..<U$.i.........
[...]
It was important to discover and document the ECC scheme used by 2Wire. When the flash contents are modified, the ECC check bits must be re-calculated for every modified flash page. We can move on now to examine the other elements in the Out-of-Band flash area.
For those interested, more general information on Hamming Code for ECC in NAND Flash can be found in [4] [5] [6] [7] [8]
[1] http://hackingbtbusinesshub.wordpress.com/2012/01/14/the-flash-header-of-an-ares-based-2wire-2701hgv-c/
[2] http://lxr.linux.no/#linux+v3.2.9/Documentation/mtd/nand_ecc.txt
[3] http://docs.google.com/leaf?id=0B6wW18mYskvBX2JOenVYMVBUWDJYSGlVQ000UTBCQQ
[4] http://www.cypress.com/?docID=19134
[5] http://www.latticesemi.com/dynamic/view_document.cfm?document_id=9622
[6] http://www.elenota.pl/datasheet_download/44776/AN1823
[7] http://www.micron.com/~/media/Documents/Products/Technical%20Note/NAND%20Flash/tn2908_NAND_hamming_ECC_code.ashx
[8] http://www.elnec.com/sw/samsung_ecc_algorithm_for_256b.pdf
