/* 
 **********************************************************************
 **  kasf.h -- header file for kasf.c                                **
 **  Implementation of Keranen's Abelian Square-Free (KASF) Sequences**
 **  Author:      Ronald L. Rivest                                   **
 **  Created:     August 2, 2005                                     **
 **  Copyright:   Freeware; Public Domain (use at your own risk)     **
 **********************************************************************
 */

/* typedef a 32 bit type */
typedef unsigned long int UINT4;

/* Data structure for KASF computation */
typedef struct {
  UINT4 C[100];                /* base-85 counter; C[0] is LS */
  UINT4 S[100];                /* state sequence resulting from 
                                  traversing C high to low */
  UINT4 L;                     /* length of C and S */
} KASF_CTX;

void KASF_Init ();             /* set to initial configuration */
unsigned char KASF_Out ();     /* get output char for current 
                                  configuration */
void KASF_Inc ();              /* advance to next configuration */


/* 
 **********************************************************************
 ** kasf.h -- end of header file                                     **
 **********************************************************************
 */
 

/* 
 **********************************************************************
 **  kasf.c                                                          **
 **  Implementation of Keranen's Abelian Square-Free (KASF) Sequences**
 **  Author:      Ronald L. Rivest                                   **
 **  Created:     August 2, 2005                                     **
 **  Copyright:   Freeware; Public Domain (use at your own risk)     **
 **********************************************************************
 */

#include <stdio.h>
#include <time.h>

/*  Magic sequence R is from:
       V. Keranen, "Abelian squares are avoidable on 4 letters", Proc.
       19th ICALP Conference, Springer LNCS vol. 623.  1992, pages 41--52.
 */
static unsigned char *R 
    = "abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca";
static unsigned int k = 85;                         /* length of R        */
static unsigned char *alphabet = "abcd";            /* alphabet used by R */
static unsigned int m = 4;                          /* size of alphabet   */

/* KASF_Init
 * Initialize KASF context to initial state.
 */
void KASF_Init(kasfContext)
KASF_CTX *kasfContext;
{ int i;
  /* Initialize length */
  kasfContext->L = 100; 
  for (i=0;i<kasfContext->L;i++) 
    {
      /* Initialize base-85 counter to zero */
      kasfContext->C[i] = 0;
      /* Initialize state sequence for traversing counter digits
         high to low.  Assumes that initial state is 0, and that
         initial state is preserved on input of counter digit 0 */
      kasfContext->S[i] = 0;
    }
}

/* KASF_Out
 * Produce output character for current state of context.
 */
unsigned char KASF_Out(kasfContext)
KASF_CTX *kasfContext;
{
  return alphabet[kasfContext->S[0]];
}

/* KASF_Inc
 * Move current context to next state.
 */
void KASF_Inc(kasfContext)
KASF_CTX *kasfContext;
{ 
  int tmp;
  int inta = (int)('a');
  int j = 0;
  while (kasfContext->C[j] == k-1)
    {  
      kasfContext->C[j] = 0; 
      j = j + 1;
    }
  kasfContext->C[j] += 1;
  tmp = kasfContext->S[j+1];
  while (j >= 0)
    { 
      tmp = (((int)(R[kasfContext->C[j]])-inta)+tmp);
      if (tmp>=m) tmp -= m;
      kasfContext->S[j] = tmp;
      j = j - 1;
    }
}

void test_kasf()
{ long i,j,n;
  time_t t1,t2;
  KASF_CTX kasfContext;

  printf("\nFirst 1700 characters:\n");
  KASF_Init(&kasfContext);
  for (i=0;i<20;i++)
    { 
      for (j=0;j<k;j++)
	{ 
	  printf("%c",KASF_Out(&kasfContext));
	  KASF_Inc(&kasfContext);
	}
      printf("\n");
    }
  printf("\n");

  printf("Generation of 10**9 bytes:\n");
  KASF_Init(&kasfContext);
  t1 = time(0);
  n = 1000000000L;
  for (i=0;i<n;i++)
    { 
      KASF_Out(&kasfContext);
      KASF_Inc(&kasfContext);
    }
  t2 = time(0);

  printf(asctime(localtime(&t1)));
  printf(asctime(localtime(&t2)));
  printf("%g seconds for %d bytes\n",difftime(t2,t1),n);
  printf("%g microseconds/byte\n",1000000.0*(double)difftime(t2,t1)/(double)n);
  printf("%g bytes per second\n\n",n/difftime(t2,t1));

  /* 
   **********************************************************************************
   * Typical output (aside from timings, which vary) (gcc -O4)
   **********************************************************************************
First 1700 characters:
abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca
bcdbdadcdadbadacabcbdbcbacbcdcacdcbdcdadbdcbcabcbdbadcdadbdacdcbdcdadbdadcadabacadcdb
cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca
cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
dabdbcbabcbdcbcacdadbdadcadabacabadbabcbdbadacdadbdcbabcbdbcabadbabcbdbcbacbcdcacbabd
cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
bcdbdadcdadbadacabcbdbcbacbcdcacdcbdcdadbdcbcabcbdbadcdadbdacdcbdcdadbdadcadabacadcdb
cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
dabdbcbabcbdcbcacdadbdadcadabacabadbabcbdbadacdadbdcbabcbdbcabadbabcbdbcbacbcdcacbabd
cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca
dabdbcbabcbdcbcacdadbdadcadabacabadbabcbdbadacdadbdcbabcbdbcabadbabcbdbcbacbcdcacbabd
cdacabadabacbabdbcdcacdcbdcdadbdadcadabacadcdbcdcacbadabacabdadcadabacabadbabcbdbadac
dabdbcbabcbdcbcacdadbdadcadabacabadbabcbdbadacdadbdcbabcbdbcabadbabcbdbcbacbcdcacbabd
bcdbdadcdadbadacabcbdbcbacbcdcacdcbdcdadbdcbcabcbdbadcdadbdacdcbdcdadbdadcadabacadcdb
dabdbcbabcbdcbcacdadbdadcadabacabadbabcbdbadacdadbdcbabcbdbcabadbabcbdbcbacbcdcacbabd
abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca
bcdbdadcdadbadacabcbdbcbacbcdcacdcbdcdadbdcbcabcbdbadcdadbdacdcbdcdadbdadcadabacadcdb
abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca

Generation of 10**9 bytes:
Wed Aug 03 23:45:32 2005
Wed Aug 03 23:45:42 2005
10 seconds for 1000000000 bytes
0.01 microseconds/byte
1e+008 bytes per second
   **********************************************************************************
   * End of expected output
   **********************************************************************************
   */
}

/* 
 **********************************************************************
 ** end of kasf.c                                                    **
 **********************************************************************
 */

/* 
 **********************************************************************
 **  dither.h                                                        **
 **  Header file for Implementation of Rivest's dither sequence      **
 **  Author:      Ronald L. Rivest                                   **
 **  Created:     August 2, 2005                                     **
 **  Copyright:   Freeware; Public Domain (use at your own risk)     **
 **********************************************************************
 */

/* typedef a 32 bit type */
/* typedef unsigned long int UINT4; */

/* Data structure for KASF computation */
typedef struct {
  UINT4 count;                 /* number of blocks processed */
  KASF_CTX kasfContext;        /* Keranen abelian square-free 
                                  sequence generator context */
} DITHER_CTX;

void DITHER_Init ();           /* go to start configuration */
unsigned int DITHER_Out ();    /* get dither output for current configuration */
void DITHER_Inc ();            /* advance configuration */


/* 
 **********************************************************************
 ** dither.h -- end of header file                                   **
 **********************************************************************
 */

/* 
 **********************************************************************
 **  dither.c                                                        **
 **  Implementation of Rivest's dither sequence                      **
 **  Author:      Ronald L. Rivest                                   **
 **  Created:     August 2, 2005                                     **
 **  Copyright:   Freeware; Public Domain (Use at your own risk)     **
 **********************************************************************
 */

/* DITHER_Init
 * Clear count and initialize Keranen abelian square-free generator
 */
void DITHER_Init(ditherContext)
DITHER_CTX *ditherContext;
{
  ditherContext->count = 0;
  KASF_Init(&ditherContext->kasfContext);
}

/* DITHER_Inc
 * Increment counter and KASF state if counter rolls over
 */
void DITHER_Inc(ditherContext)
DITHER_CTX *ditherContext;
{
  ditherContext->count++;
  if (ditherContext->count >= 8192)
    {
      ditherContext->count = 0;
      KASF_Inc(&ditherContext->kasfContext);
    }
}

/* DITHER_Out
 * Produce output value (16 bit) for current dither count and state
 */
unsigned int DITHER_Out(ditherContext, last, last_count)
DITHER_CTX *ditherContext;
unsigned int last;            /* nonzero if last block */
unsigned int last_count;      /* number of bits in last block if last != 0 */
{
  unsigned int output;
  unsigned char kasf_char;
  unsigned int kasf_bits;
  if (last == 0) /* not the last block */
    {
      output = ditherContext->count;
      kasf_char = KASF_Out(&ditherContext->kasfContext);
      kasf_bits = kasf_char-(int)('a');
      output ^= (kasf_bits<<13);
      return output;
    }
  /* last block */
  output = 0x8000 | (last_count & 0x7FFF);
  return output;
}

/* test_dither
 * Produce and print dither input sequence for 25,001 blocks,
 * where the last block has size 240 (bits).
 */
void test_dither()
{ 
  unsigned long int i;
  DITHER_CTX ditherContext;
  DITHER_Init(&ditherContext);
  for (i = 0;i<25000;i++)
    {
      if ((i%16)==0) 
	printf("\n%c ",KASF_Out(&ditherContext.kasfContext));
      printf("%04x ",DITHER_Out(&ditherContext,0,0));
      DITHER_Inc(&ditherContext);
    }
  /* Now produce dither for last block (240-bit block. 240 = 0xF0 ) */
  printf("\nLast block dither: %04x \n",DITHER_Out(&ditherContext,1,240));
 
}

/* 
 ********************************************************************************
 * Expected output of test_dither
 * Sequence of 16-bit values, 16 per line, in hexadecimal.
 * Each 16-bit value contains last-block flag, two-bit Keranen sequence value,
 *   and a 13-bit counter.  The Keranen sequence value only changes every 8192
 *   outputs.  The single letter at the beginning of each line says what 
 *   Keranen sequence value (a=00,b=01,c=10,or d=11) is contained within each
 *   sequence value on that line; that letter is not part of the official 
 *   dither output sequence.
 ********************************************************************************
a 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 000a 000b 000c 000d 000e 000f 
a 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 001a 001b 001c 001d 001e 001f 
...
a 1fe0 1fe1 1fe2 1fe3 1fe4 1fe5 1fe6 1fe7 1fe8 1fe9 1fea 1feb 1fec 1fed 1fee 1fef 
a 1ff0 1ff1 1ff2 1ff3 1ff4 1ff5 1ff6 1ff7 1ff8 1ff9 1ffa 1ffb 1ffc 1ffd 1ffe 1fff 
b 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 200a 200b 200c 200d 200e 200f 
b 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 201a 201b 201c 201d 201e 201f 
...
b 3fe0 3fe1 3fe2 3fe3 3fe4 3fe5 3fe6 3fe7 3fe8 3fe9 3fea 3feb 3fec 3fed 3fee 3fef 
b 3ff0 3ff1 3ff2 3ff3 3ff4 3ff5 3ff6 3ff7 3ff8 3ff9 3ffa 3ffb 3ffc 3ffd 3ffe 3fff 
c 4000 4001 4002 4003 4004 4005 4006 4007 4008 4009 400a 400b 400c 400d 400e 400f 
c 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 401a 401b 401c 401d 401e 401f 
...
c 5fe0 5fe1 5fe2 5fe3 5fe4 5fe5 5fe6 5fe7 5fe8 5fe9 5fea 5feb 5fec 5fed 5fee 5fef 
c 5ff0 5ff1 5ff2 5ff3 5ff4 5ff5 5ff6 5ff7 5ff8 5ff9 5ffa 5ffb 5ffc 5ffd 5ffe 5fff 
a 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 000a 000b 000c 000d 000e 000f 
a 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 001a 001b 001c 001d 001e 001f 
...
Last block dither: 80f0 
 ********************************************************************************
 * End of expected output for test_dither
 ********************************************************************************
 */

/* 
 **********************************************************************
 ** end of dither.c                                                  **
 **********************************************************************
 */

int main()
{
  test_kasf();
  test_dither();
  return (0);
}