CRC routines as PRNGs

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

Hey all, 10 years later, I've figured out a better way to generalize the "shortcut" method of clocking a Galois LFSR multiple times in one go. Apologies if I'm covering old ground, but I've actually come back to this thread several times for reference, which is why I'm updating it instead of making a new one. :P

This is an example of shifting 9 bits in one go. Assume left shifts, and tap 0 is the LSB of the shift register. Dots and Spaces are zeroes. To switch to right shifts, read these instructions through a mirror. ;) (I'm serious, align MSBs instead of LSBs, reverse bit order, and switch to right shifts)

Code: Select all

Taps       C      5    0
Input   abcdefghijklmnop

== Calculate Feedback ==
<<9      abcdefghi  <-  jklmnop.........
Tap C        abcde  <-  fghi............
Tap C            a  <-  bcde............
         ---XOR---
Feedback ABCDEFGHI

== Shift ==
<<9     jklmnop.........
Tap C   FGHI............
Tap 5     ABCDEFGHI.....
Tap 0          ABCDEFGHI
        -------XOR------
The 9-bit shift is so you can see how Tap C's feedback actually overflows twice recursively. If you shift 8 bits instead, Tap C only overflows once and you skip a shift/xor.

To use this to make your own "shortcut" Galois LFSR, decide how many bits you'll shift at a time, then look at what bit-shifting equations (like the ones above) it makes, given your taps. It's then up to you to come up with efficient code to perform all of the shifts and XORs to calculate the feedback, then calculate the result.

I've tested this with 500 iterations against the normal bit-by-bit version, and unless I've made a typo, this works. I've tried up to 16-bit shifts and it generates correct output.
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: CRC routines as PRNGs

Post by rainwarrior »

A few years ago someone brought up CRC routines that essentially do 8 LFSR ticks at a time, and I ended up applying the concept to 16, 24, and 32 bit LFSRs, which I published here: Github: prng_6502

With those, I did a brute force search of all taps that gave maximal length, which had properties that I thought would result in minimal computation in the 8x version, and from those I tried to pick the one that would be fastest.
User avatar
aquasnake
Posts: 515
Joined: Fri Sep 13, 2019 11:22 pm

Re: CRC routines as PRNGs

Post by aquasnake »

u16 crcFast(void *src, u16 len) {

u8 *ptr8 = (u8 *) src;
u8 crc1 = 0;
u8 crc2 = 0;

while (len--) {
crc1 += *ptr8++;
crc2 = (crc1 + crc2);
}

return (crc1 << 8) | crc2;
}

Code extracted from krikzz' project
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: CRC routines as PRNGs

Post by Drag »

rainwarrior wrote: Fri Jun 17, 2022 5:28 pm A few years ago someone brought up CRC routines that essentially do 8 LFSR ticks at a time, and I ended up applying the concept to 16, 24, and 32 bit LFSRs, which I published here: Github: prng_6502

With those, I did a brute force search of all taps that gave maximal length, which had properties that I thought would result in minimal computation in the 8x version, and from those I tried to pick the one that would be fastest.
Yep! Thanks for your work on that. :D
User avatar
aquasnake
Posts: 515
Joined: Fri Sep 13, 2019 11:22 pm

Re: CRC routines as PRNGs

Post by aquasnake »

Code: Select all

static const unsigned char rnd_list[] = {
    0xfe, 0xc9, 0xd4, 0x45, 0xd8, 0xf6, 0x4e, 0x89, 
    0x3a, 0x1b, 0x36, 0x16, 0xbd, 0xc5, 0xc1, 0x73, 
    0xdb, 0xb2, 0xda, 0xcd, 0x3a, 0x7e, 0x97, 0x64, 
    0x22, 0x01, 0x1f, 0x87, 0x48, 0xb5, 0xc7, 0xdd, 
    0x90, 0xe4, 0xc4, 0x6f, 0xe1, 0x95, 0x8f, 0x29, 
    0xbd, 0x6b, 0x49, 0x8d, 0x7c, 0xc0, 0x62, 0x38, 
    0x87, 0x7d, 0xbd, 0xdc, 0x0f, 0xbe, 0x54, 0x43, 
    0x18, 0xbf, 0x7e, 0x8e, 0xfb, 0x65, 0xa9, 0xde, 
    0xc8, 0x85, 0xb5, 0x43, 0xd1, 0x23, 0xeb, 0x28, 
    0x03, 0x9e, 0x08, 0xb5, 0x53, 0x57, 0x57, 0x86, 
    0xf7, 0x32, 0xf9, 0xa3, 0x38, 0xa6, 0xbf, 0xf9, 
    0x07, 0x2c, 0xa4, 0x78, 0x81, 0x17, 0xaa, 0x6c, 
    0x00, 0x5b, 0x29, 0x48, 0x27, 0x0c, 0xa5, 0x51, 
    0x15, 0x01, 0xc8, 0x95, 0x5e, 0xb5, 0x70, 0x23, 
    0x91, 0xfc, 0x08, 0x33, 0x51, 0x68, 0x19, 0x25, 
    0x90, 0x94, 0xc1, 0xa5, 0x57, 0xd7, 0x52, 0xdf, 
    0x88, 0xd7, 0x5d, 0x3b, 0xe6, 0xc1, 0x92, 0x0d, 
    0x94, 0x91, 0xfb, 0x3d, 0x26, 0x43, 0xfa, 0x4d, 
    0xb6, 0x51, 0x0d, 0xac, 0x6f, 0x3d, 0x32, 0xb7, 
    0x1d, 0x25, 0x18, 0x82, 0x0e, 0x3e, 0x03, 0x0e, 
    0x9c, 0x1c, 0x27, 0x13, 0x40, 0xeb, 0xa7, 0x50, 
    0x53, 0x29, 0x58, 0x7f, 0xaa, 0xf2, 0x2f, 0x3c, 
    0x1a, 0xe4, 0x61, 0xe0, 0xef, 0x86, 0x09, 0xba, 
    0x4c, 0xfd, 0xc5, 0xbf, 0x71, 0x75, 0x3e, 0x0e, 
    0x82, 0xc2, 0xa5, 0xe7, 0x5a, 0x34, 0x32, 0xd0, 
    0xec, 0x54, 0xe7, 0x66, 0x5b, 0x3e, 0xf5, 0xc6, 
    0x35, 0x74, 0x2c, 0xba, 0x89, 0x49, 0xbd, 0xca, 
    0x80, 0xb1, 0x7e, 0x0d, 0x60, 0xec, 0x1e, 0xf7, 
    0xd4, 0x3d, 0x88, 0xfb, 0x1d, 0xbe, 0x1a, 0x58, 
    0x07, 0x8f, 0x23, 0x14, 0x3d, 0x47, 0x91, 0x75, 
    0xd9, 0x28, 0x02, 0x4f, 0xff, 0x8b, 0x94, 0x46, 
    0x3e, 0x14, 0x25, 0xb3, 0x31, 0xf7, 0x19, 0xb6
};

unsigned char rnd_seed = 0;

unsigned char getrndnum(unsigned char below)
{
    static unsigned char counter = 0;
    counter++;
    return rnd_list[rnd_seed+counter]%below;
}
The counter can be replaced by the system time or RTC readout value. For the tiny MCU system without RTC, the static counter in the function or the counter in the NMI sub routine is used instead.

Code: Select all

static const u32 crc32tab[] = {
    0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL,
    0x076dc419L, 0x706af48fL, 0xe963a535L, 0x9e6495a3L,
    0x0edb8832L, 0x79dcb8a4L, 0xe0d5e91eL, 0x97d2d988L,
    0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L, 0x90bf1d91L,
    0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
    0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L,
    0x136c9856L, 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL,
    0x14015c4fL, 0x63066cd9L, 0xfa0f3d63L, 0x8d080df5L,
    0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L, 0xa2677172L,
    0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
    0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L,
    0x32d86ce3L, 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L,
    0x26d930acL, 0x51de003aL, 0xc8d75180L, 0xbfd06116L,
    0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L, 0xb8bda50fL,
    0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
    0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL,
    0x76dc4190L, 0x01db7106L, 0x98d220bcL, 0xefd5102aL,
    0x71b18589L, 0x06b6b51fL, 0x9fbfe4a5L, 0xe8b8d433L,
    0x7807c9a2L, 0x0f00f934L, 0x9609a88eL, 0xe10e9818L,
    0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
    0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL,
    0x6c0695edL, 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L,
    0x65b0d9c6L, 0x12b7e950L, 0x8bbeb8eaL, 0xfcb9887cL,
    0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L, 0xfbd44c65L,
    0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
    0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL,
    0x4369e96aL, 0x346ed9fcL, 0xad678846L, 0xda60b8d0L,
    0x44042d73L, 0x33031de5L, 0xaa0a4c5fL, 0xdd0d7cc9L,
    0x5005713cL, 0x270241aaL, 0xbe0b1010L, 0xc90c2086L,
    0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
    0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L,
    0x59b33d17L, 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL,
    0xedb88320L, 0x9abfb3b6L, 0x03b6e20cL, 0x74b1d29aL,
    0xead54739L, 0x9dd277afL, 0x04db2615L, 0x73dc1683L,
    0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
    0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L,
    0xf00f9344L, 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL,
    0xf762575dL, 0x806567cbL, 0x196c3671L, 0x6e6b06e7L,
    0xfed41b76L, 0x89d32be0L, 0x10da7a5aL, 0x67dd4accL,
    0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
    0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L,
    0xd1bb67f1L, 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL,
    0xd80d2bdaL, 0xaf0a1b4cL, 0x36034af6L, 0x41047a60L,
    0xdf60efc3L, 0xa867df55L, 0x316e8eefL, 0x4669be79L,
    0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
    0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL,
    0xc5ba3bbeL, 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L,
    0xc2d7ffa7L, 0xb5d0cf31L, 0x2cd99e8bL, 0x5bdeae1dL,
    0x9b64c2b0L, 0xec63f226L, 0x756aa39cL, 0x026d930aL,
    0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
    0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L,
    0x92d28e9bL, 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L,
    0x86d3d2d4L, 0xf1d4e242L, 0x68ddb3f8L, 0x1fda836eL,
    0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L, 0x18b74777L,
    0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
    0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L,
    0xa00ae278L, 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L,
    0xa7672661L, 0xd06016f7L, 0x4969474dL, 0x3e6e77dbL,
    0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L, 0x37d83bf0L,
    0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
    0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L,
    0xbad03605L, 0xcdd70693L, 0x54de5729L, 0x23d967bfL,
    0xb3667a2eL, 0xc4614ab8L, 0x5d681b02L, 0x2a6f2b94L,
    0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL, 0x2d02ef8dL 
};

u32 crc32(u8 *src, u32 len) 
{
    u32 i, crc_base = 0xFFFFFFFF;

    for (i = 0; i < len; i++)
        crc_base = crc32tab[(crc_base ^ *(src + i)) & 0xff] ^ (crc_base >> 8);
    crc_base ^= 0xFFFFFFFF;
    return crc_base;
}
Oziphantom
Posts: 1565
Joined: Tue Feb 07, 2017 2:03 am

Re: CRC routines as PRNGs

Post by Oziphantom »

for the CRC cases
8bit with valid EOR values here https://codebase64.org/doku.php?id=base ... 8-bit_prng
16bit with valid EOR values here https://codebase64.org/doku.php?id=base ... 6-bit_prng

a 2->16bit Galois here https://codebase64.org/doku.php?id=base ... alois_lfsr
Post Reply