lfsr.c

#include <stdio.h>
#include <stdint.h>
#include "utils.h"

// tap bit vectors
// 32 bit: 11100001111101000100001111110000 period32: 0xffffffff, total running time 20.786127337
// 31 bit: 01111011101110001000100010001000 period31: 0x7fffffff, total running time 10.-689482807
// 29 bit: 00010111000100100001000100000000 period29: 0x1fffffff, total running time 1.470057247
// 27 bit: 00000100110011010001010111101010 period27: 0x07ffffff, total running time 1.-415052525

// these bitvectors for the taps have been extracted by taking the
// lookuptable from the c reversed code, and starting from the 15th
// element 16 bytes and transposing their bits. the py fn extract()
// below was used to do so.

// bit equation generated by running  ' ^ '.join(f'(lfsr >> {i})' for i, x in enumerate(reversed(str(tapbitvector))) if x=='1')

// the start and end constants for each were generated by
// initializing the original "big" lfsr loop of the px1k algo
// lfsr0 is this initial state
// in our case: lfsr0=unhexlify("f078d21e0f693c875ac3d2d2692d3cff")
// run the loop as intended 32 times to generate the next state of the lfsr
// lfsr1 is the next state
// in our case: lfsr1=unhexlify("dc5bf4e8330fe0807497b02eb71085b0")
// then extract the 32bit vector for the initial and final state for the sub-lfsr by running the following python function:
//
// def extract(lfsr, i):
//     # left to right
//     tr = [''.join(str((lfsr[j] >> b) & 1) for j in range(16)) for b in range(8)]
//     # horizontal bottoms-up lines appended
//     return (tr[(i*2)+1]+tr[(i*2)])
// as such
// start32 = extract(lfsr0,0)
// final32 = extract(lfsr1,0)
// start31 = extract(lfsr0,1)
// final31 = extract(lfsr1,1)
// start29 = extract(lfsr0,2)
// final29 = extract(lfsr1,2)
// start27 = extract(lfsr0,3)
// final27 = extract(lfsr1,3)

static unsigned long lfsr32(const uint32_t start, const uint32_t final) {
  printf("s: %08x e: %08x\n", start, final);
  uint32_t lfsr = start;
  unsigned bit;
  unsigned long period = 0;
  do {
      bit = ((lfsr >> 4) ^ (lfsr >> 5) ^ (lfsr >> 6) ^ (lfsr >> 7) ^ (lfsr >> 8) ^ (lfsr >> 9) ^ (lfsr >> 14) ^ (lfsr >> 18) ^ (lfsr >> 20) ^ (lfsr >> 21) ^ (lfsr >> 22) ^ (lfsr >> 23) ^ (lfsr >> 24) ^ (lfsr >> 29) ^ (lfsr >> 30) ^ (lfsr >> 31)) & 1;
      lfsr =  (lfsr << 1) | bit;
      ++period;
      if(lfsr == start || period >= 1UL<<32) {
        return -1;
      }
    } while(lfsr != final);
  return period;
}


static unsigned long lfsr31(const uint32_t start, const uint32_t final) {
  printf("s: %08x e: %08x\n", start, final);
  uint32_t lfsr = start;
  unsigned bit;
  unsigned long period = 0;
  do {
      bit = ((lfsr >> 3) ^ (lfsr >> 7) ^ (lfsr >> 11) ^ (lfsr >> 15) ^ (lfsr >> 19) ^ (lfsr >> 20) ^ (lfsr >> 21) ^ (lfsr >> 23) ^ (lfsr >> 24) ^ (lfsr >> 25) ^ (lfsr >> 27) ^ (lfsr >> 28) ^ (lfsr >> 29) ^ (lfsr >> 30)) & 1;
      lfsr =  (lfsr << 1) | bit;
      ++period;
      //if(period==0x20) {
      //  int i;
      //  for(i=31;i>=0;i--) printf("%d",(lfsr >> i) & 1);
      //  printf("\n");
      //}
      if(lfsr == start || period >= 1UL<<31) {
        return -1;
      }
    } while(lfsr != final);
  return period;
}

static unsigned long lfsr29(const uint32_t start, const uint32_t final) {
  printf("s: %08x e: %08x\n", start, final);
  uint32_t lfsr = start;
  unsigned bit;
  unsigned long period = 0;
  do {
      bit = ((lfsr >> 8) ^ (lfsr >> 12) ^ (lfsr >> 17) ^ (lfsr >> 20) ^ (lfsr >> 24) ^ (lfsr >> 25) ^ (lfsr >> 26) ^ (lfsr >> 28)) & 1;
      lfsr =  (lfsr << 1) | bit;
      ++period;
      if(lfsr == start || period >= 1UL<<29) {
        return -1;
      }
    } while(lfsr != final);
  return period;
}

static unsigned long lfsr27(const uint32_t start, const uint32_t final) {
  printf("s: %08x e: %08x\n", start, final);
  uint32_t lfsr = start;
  unsigned bit;
  unsigned long period = 0;
  do {
      bit = ((lfsr >> 1) ^ (lfsr >> 3) ^ (lfsr >> 5) ^ (lfsr >> 6) ^ (lfsr >> 7) ^ (lfsr >> 8) ^ (lfsr >> 10) ^ (lfsr >> 12) ^ (lfsr >> 16) ^ (lfsr >> 18) ^ (lfsr >> 19) ^ (lfsr >> 22) ^ (lfsr >> 23) ^ (lfsr >> 26)) & 1;
      lfsr =  (lfsr << 1) | bit;
      ++period;
      if(lfsr == start || period >= 1UL<<27) {
        return -1;
      }
      bindump((unsigned char*) &lfsr, 4);
    } while(lfsr != final);
  return period;
}

static void assemble(const uint32_t lfsrs[4], uint8_t *l) {
  
}

int main(void) {
  if(0x20!= lfsr32(0x39f10d4d, 0x4c584c4a)) return 1;
  if(0x20!= lfsr31(0x5e8f1b07, 0xd410a4da)) return 1;
  if(0x20!= lfsr29(0xc60ff2b3, 0x3ab9e8ed)) return 1;
  if(0x20!= lfsr27(0xa171e4f9, 0xb36bf280)) return 1;
  return 0;
}