Winbond W25N01GV NAND ECC Algorithm - Complete Reverse Engineering

This document describes the complete reverse-engineered ECC (Error Correction Code) algorithm for the Winbond W25N01GV Serial NAND flash chip. Both the Main Sector ECC and Spare Area ECC have been fully decoded and verified against a full NAND dump with 100% accuracy.

---

Overview

The Winbond W25N01GV organizes data into pages of 2112 bytes each:

• 4 × 512-byte sectors = 2048 bytes of main data
• 4 × 16-byte spare areas = 64 bytes of OOB (Out-Of-Band) data

Each 512-byte sector has a 6-byte ECC stored in its corresponding spare area at offset 8-13. Each 16-byte spare area has a 2-byte ECC stored at offset 14-15, which protects the first 10 bytes of the spare area (bytes 4-13).

Spare Area Layout (16 bytes)

Offset	Size	Description	Value in nand.bin
0-1	2	Bad block marker	0xFFFF
2-3	2	User Data II	0xFFFF
4-7	4	User Data I	0xFFFFFFFF
8-13	6	Sector ECC (for 512-byte sector)	Computed
14-15	2	Spare ECC (for bytes 4-13)	Computed

---

Main Sector ECC Algorithm

Purpose: Compute 6 bytes of ECC for a 512-byte sector (3 bytes per 256-byte sub-sector)

Algorithm

The ECC is based on Hamming code with additional parity correction. For each 256-byte sub-sector:

Step 1: Compute Hamming Syndrome

syn = 0
for byte_pos in range(256):
    bv = sub_sector[byte_pos]
    for i in range(8):
        if bv & (1 << i):
            syn ^= (byte_pos * 8 + i)

The syndrome is the XOR of all bit positions where a 1 bit occurs. For a 256-byte sector, this produces an 11-bit syndrome (8 bits for byte position + 3 bits for bit position within byte).

Step 2: Count Total Bits

total_bits = sum(bin(b).count('1') for b in sub_sector)

Count the total number of 1 bits in the sub-sector.

Step 3: Parity Correction

parity = 0xff if total_bits % 2 == 1 else 0

This is an overall parity byte: 0xFF if odd number of bits, 0x00 if even.

Step 4: Compute ECC Byte 0

byte0 = (syn & 0xff) ^ parity

The lower 8 bits of the syndrome, XORed with the parity.

Step 5: Compute ECC Byte 1

syn08 = syn & 0xff          # Lower 8 bits of syndrome
syn811 = (syn >> 8) & 0x07  # Upper 3 bits of syndrome (bits 8-10)

# Compute intermediate value g
g = ((syn08 & 0x0f) << 12) | (syn811 << 4) | (syn08 >> 4)

# Apply total_bits parity correction
extra_13 = g ^ ((total_bits & 1) << 11)

# Byte 1 combines upper bits of extra_13 with XOR of syn811 and parity
byte1 = ((extra_13 >> 8) & 0xff) | (syn811 ^ (0x07 if total_bits % 2 == 1 else 0))

Step 6: Compute ECC Byte 2

byte2 = extra_13 & 0xff

The lower 8 bits of the intermediate value.

Complete Implementation (Python)

def compute_subsector_ecc(sub):
    """Compute 3-byte ECC for a 256-byte sub-sector."""
    # Step 1: Compute Hamming syndrome
    syn = 0
    for byte_pos in range(256):
        bv = sub[byte_pos]
        for i in range(8):
            if bv & (1 << i):
                syn ^= (byte_pos * 8 + i)
    
    # Step 2: Count total bits
    total_bits = sum(bin(b).count('1') for b in sub)
    
    # Step 3: Parity
    parity = 0xff if total_bits % 2 == 1 else 0
    
    # Step 4: byte0
    byte0 = (syn & 0xff) ^ parity
    
    # Step 5: byte1 and byte2
    syn08 = syn & 0xff
    syn811 = (syn >> 8) & 0x07
    
    g = ((syn08 & 0x0f) << 12) | (syn811 << 4) | (syn08 >> 4)
    extra_13 = g ^ ((total_bits & 1) << 11)
    
    b1_high = extra_13 >> 8
    b1_low = syn811 ^ (0x07 if total_bits % 2 == 1 else 0)
    byte1 = b1_high | b1_low
    
    byte2 = extra_13 & 0xff
    
    return byte0, byte1, byte2


def compute_sector_ecc(sector_data):
    """Compute 6-byte ECC for a 512-byte sector."""
    sub1 = sector_data[0:256]
    sub2 = sector_data[256:512]
    
    b0_1, b1_1, b2_1 = compute_subsector_ecc(sub1)
    b0_2, b1_2, b2_2 = compute_subsector_ecc(sub2)
    
    return bytes([b0_1, b1_1, b2_1, b0_2, b1_2, b2_2])

Key Properties

1. Deterministic: Same input data always produces the same ECC
2. Linear over GF(2): ECC of XORed data = XOR of individual ECCs
3. Erased state: All 0xFF data produces all 0x00 ECC
4. Hamming-based: Uses 11-bit syndrome for single-bit error correction and 2-bit error detection

---

Spare Area ECC Algorithm

Purpose: Compute 2 bytes of ECC for 10 bytes of spare data (User Data I + Sector ECC)

Algorithm

The Spare ECC follows the same Hamming code principle as the Main Sector ECC, but over only 10 input bytes.

The two output bytes are always identical, providing redundancy for error detection in the spare area itself.

Input

• 10 bytes = spare[4:14] = User Data I (4 bytes) + Sector ECC (6 bytes)

Output

• 2 bytes = spare[14:16] where both bytes are identical

Step 1: Compute Hamming Syndrome

syn = 0
for byte_pos in range(10):
    bv = input_bytes[byte_pos]
    for i in range(8):
        if bv & (1 << i):
            syn ^= (byte_pos * 8 + i)

The syndrome is the XOR of all bit positions where a 1 bit occurs. For 10 input bytes, this produces a syndrome value that captures the position of all set bits.

Step 2: Count Total Bits

total_bits = sum(popcount(b) for b in input_bytes)

Count the total number of 1 bits in the 10 input bytes.

Step 3: Parity Correction

parity = 0xff if total_bits % 2 == 1 else 0

This is an overall parity byte: 0xFF if odd number of bits, 0x00 if even.

Step 4: Compute ECC Byte

ecc_byte = (syn & 0xff) ^ parity

The lower 8 bits of the syndrome, XORed with the parity byte.

Step 5: Return Both Bytes (Identical)

return bytes([ecc_byte, ecc_byte])

Both output bytes are set to the same computed ECC byte for redundancy.

Complete Implementation (Python)

def compute_spare_ecc(input_bytes):
    """Compute 2-byte Spare ECC from 10 input bytes.
    
    Args:
        input_bytes: 10 bytes from spare[4:14] = User Data I (4 bytes) + Sector ECC (6 bytes)
        
    Returns:
        2 bytes where both bytes are identical (spare[14:16])
    """
    # Step 1: Compute Hamming syndrome
    syn = 0
    for byte_pos in range(10):
        bv = input_bytes[byte_pos]
        for i in range(8):
            if bv & (1 << i):
                syn ^= (byte_pos * 8 + i)
    
    # Step 2: Count total bits
    total_bits = sum(bin(b).count('1') for b in input_bytes)
    
    # Step 3: Compute parity
    parity = 0xff if total_bits % 2 == 1 else 0
    
    # Step 4: Compute ECC byte
    ecc_byte = (syn & 0xff) ^ parity
    
    # Step 5: Return both bytes (identical)
    return bytes([ecc_byte, ecc_byte])

Caveat: User Data I

In the NAND dump made, User Data I (spare[4:8]) is always 0xFFFFFFFF. This is significant:

• The syndrome contribution from 0xFFFFFFFF is 0 (XOR of all bit positions 0-31 = 0)
• The parity contribution is also 0 (32 bits is even)
• Therefore, the Spare ECC depends only on the Sector ECC bytes (spare[8:14])

However, the algorithm should work for any input values, not just the observed 0xFFFFFFFF.

---

Complete Page ECC Computation

To compute all ECC for a complete 2112-byte page:

def compute_page_ecc(page_data):
    """Compute all ECC bytes for a 2112-byte page.
    
    Returns:
        dict with 'sector_ecc' and 'spare_ecc' lists
    """
    sector_ecc = []
    spare_ecc = []
    
    # Compute Sector ECC for each of 4 sectors
    for i in range(4):
        sector = page_data[i*512:(i+1)*512]
        ecc = compute_sector_ecc(sector)
        sector_ecc.append(ecc)
    
    # Compute Spare ECC for each of 4 spare areas
    for i in range(4):
        spare_start = 2048 + i * 16
        spare = page_data[spare_start:spare_start+16]
        input_bytes = bytes(spare[4:14])
        ecc = compute_spare_ecc(input_bytes)
        spare_ecc.append(ecc)
    
    return {'sector_ecc': sector_ecc, 'spare_ecc': spare_ecc}

---

Regenerating a full NAND with OOB from a NAND without any

A NAND dump without OOB contains only the 2048 bytes of sector data per page (no spare areas). The following process regenerates a complete NAND with OOB including ECC:

1. For each page:

   • Copy sector data (2048 bytes)
   • If all sectors are 0xFF (erased page):
     • Set all spare bytes to 0xFF
   • Else:
     • For each sector:
       • Compute 6-byte Sector ECC
     • For each spare area:
       • Set spare[0:2] = 0xFFFF (Bad block marker)
       • Set spare[2:4] = 0xFFFF (User Data II)
       • Set spare[4:8] = 0xFFFFFFFF (User Data I)
       • Set spare[8:14] = Sector ECC
       • Compute Spare ECC from spare[4:14]
       • Set spare[14:16] = Spare ECC

2. Result: 100% binary match to performed dumps

---

Theoretical Foundation

The algorithm is based on Hamming code principles:

1. Syndrome Computation: Each bit position (byte × 8 + bit) is XORed into a syndrome value
2. Parity: An overall parity bit is added for odd/even bit count detection
3. Error Correction: The 11-bit syndrome can identify and correct single-bit errors
4. Error Detection: Can detect 2-bit errors (but not correct them)

From the Winbond datasheet:

"As the ECC engine is based on Hamming code, the ECC status bits are applicable for 1 bit ECC correction and 2 bit ECC detection."

Why the Algorithm Works

• Linearity: The ECC is linear over GF(2), meaning ECC(A ⊕ B) = ECC(A) ⊕ ECC(B)
• Determinism: Same data always produces same ECC
• Erased State: All 0xFF data has no bits set, so syndrome = 0 and parity = 0, resulting in ECC = 0x00
• Hamming Structure: The syndrome captures enough information to locate single-bit errors

---

Implementation Notes

File Structure

src/
├── complete_ecc.py      # Main Sector ECC implementation
├── spare_ecc.py         # Spare Area ECC implementation
├── full_ecc.py          # Combined verification
└── regenerate_nand.py   # Complete nand.bin regeneration

Usage Examples

# Verify Sector ECC
python3 src/complete_ecc.py

# Verify Spare ECC
python3 src/spare_ecc.py

# Verify combined ECC
python3 src/full_ecc.py

# Regenerate nand.bin from nand_clean.bin
python3 src/regenerate_nand.py --verify

---

Conclusion

The complete Winbond W25N01GV ECC algorithm has been successfully reverse-engineered. Both the Main Sector ECC and Spare Area ECC have been verified against all available data with 100% accuracy. The algorithm is based on Hamming code with parity correction, providing 1-bit error correction and 2-bit error detection capability.