[index] [home]

Tweet

NES lockout-chip address smartness



This text describes a weird address-incrementing scheme as used on the NES lockout-chip, which I had never seen before.

Quite pretty and interesting :-)

Update: LFSR

(This page was originally written before I heard the term "LFSR" - thank you people!)

The mechanism used here is actually called a linear feedback shift-register (LFSR).

So-called "maximum-cycle" LFSRs have period 2n - 1. While for example this document shows where to place XOR-"taps" for a n-stage LSFR to get this maximum cycle-length, the implementation in the NES-chip uses XNOR-taps at the 2 LSB-bits.

Introduction

The Nintendo Entertainment System (NES) was a game-console released in 1983, and used a lockout-chip (Checking Integrated Circuit - CIC) to prevent release and distribution of unlicensed games.

The chip could operate in either key- or lock-mode.

One lock-mode chip was built into the console itself, and each cartridge would contain a key-mode chip. If the key was not present (e.g. on a pirated or foreign-region cartridge), the lock would keep the console in reset, effectively preventing the game from being run.

The chip was in fact a Sharp 4-bit microcontroller, doing a random challenge-response between console and cartridge.

Smartness

Whereas a 'normal' CPU or microcontroller would auto-increment its program counter (PC) with every instruction cycle assuming no branch was taken, the CIC used a different scheme, as described on this wonderful page about reverse-engineering the CIC ROM.

Algorithm to advance PC, instead of "simply add 1", is as follows:

That's it.

How well does this work?

Although I am not math-savvy enough to fully understand why, this trick works remarkably well - that is, when starting at address 'all-zeroes' and thus advancing until 'all-zeroes' occurs again, the resulting sequence-length is quite high.

Note that 'all-ones' is a 'stuck' situation: the new MSB shifted in would always be '1', because bits 0 and 1 are both '1'. Thus, the bit pattern would never change.

Furthermore, the only way to get to 'all-ones', is from 'all-ones'.

Therefore, the bit pattern 'all-ones' does not occur in any sequence longer than 1. (And therefore, for a word-size of N bits, the resulting sequence-length is at most (2N)-1 .)

Examples

To print sequences of bit patterns for a given word-size, I used the following Tcl program:

    #!/usr/bin/env tclsh



    # Calculate successor for a given bit pattern.

    proc succ { li } {

        set msb [ lindex $li 0 ]

        set lsb_1 [ lindex $li end-1 ]
        set lsb_0 [ lindex $li end   ]

        set new_msb [ expr { $lsb_1 == $lsb_0 } ]

        concat $new_msb [ lrange $li 0 end-1 ]
    }



    # Calculate sequence-length for a given word-size, when starting at 'all-zeroes'.
    # (A sequence ends when 'all-zeroes' is encountered again.)

    proc seqlen nbit {

        puts "--- $nbit bits: ---"

        set curr [ lrepeat $nbit 0 ]

        set seen {}

        set seqlen 0

        while { $curr ni $seen } {

            puts [ format {  %-3d: %s} $seqlen [ join $curr {} ] ]

            lappend seen $curr
            set curr [ succ $curr ]

            incr seqlen
        }

        puts {}

        expr $seqlen
    }



    # Gather and print sequence-lengths for each word-size.

    for { set nbit 2 } { $nbit <= 16 } { incr nbit } {

        dict set result $nbit [ seqlen $nbit ]
    }

    dict for { nbit seqlen } $result {

        set missing [ expr { 2 ** $nbit  -  $seqlen } ]
        puts "$nbit bits --> seqlen = $seqlen (missing: $missing)"
    }

It outputs the generated bit patterns for each word-size, when starting from 'all-zeroes' and advancing until 'all-zeroes' is encountered for the second time:

    --- 2 bits: ---
      0  : 00
      1  : 10
      2  : 01

    --- 3 bits: ---
      0  : 000
      1  : 100
      2  : 110
      3  : 011
      4  : 101
      5  : 010
      6  : 001

    --- 4 bits: ---
      0  : 0000
      1  : 1000
      2  : 1100
      3  : 1110
      4  : 0111
      5  : 1011
      6  : 1101
      7  : 0110
      8  : 0011
      9  : 1001
      ...
      ...

...all the way up to 16 bits. Which takes a while to compute.

The resulting sequence-lengths:

For the word-sizes in bold, the sequence has optimal length. Optimal sequences occur even as far as 15 bit word-size. Wow!

(I didn't check beyond 16 bits.)

Caveat

The sequence of instructions as executed would not match their sequence in program-memory at all. I guess this is not so much of a problem when using an assembler supporting symbolic address-labels.

As explained in the aforementioned article about the CIC program, the PC is 10 bits wide; only 512 bytes of ROM were implemented, and the ROM was divided into banks of 128 bytes (7 bits - an optimal sequence-length :-). Advancing the PC would never cross a bank-boundary - only an unconditional jump-instruction could.


Delivered to you by Vim, GNU Make, MultiMarkdown, bozohttpd, NetBSD, and 1 human.