Fix bug dividing small things by large ones.

[u/mdw/catacomb] / blowfish-mktab.c

/* -*-c-*-
 *
 * $Id: blowfish-mktab.c,v 1.2 2000/07/16 12:33:11 mdw Exp $
 *
 * Build Blowfish key table
 *
 * (c) 2000 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: blowfish-mktab.c,v $
 * Revision 1.2  2000/07/16 12:33:11  mdw
 * Shut stupid compiler up.
 *
 * Revision 1.1  2000/06/17 10:47:28  mdw
 * Emits Blowfish initial key data, derived from the digits of pi.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#include <mLib/bits.h>

/*----- Main code ---------------------------------------------------------*/

/* --- @spigot@ --- *
 *
 * Arguments:	@uint32 *buf@ = pointer to the output buffer
 *		@size_t n@ = number of output digits wanted
 *
 * Returns:	---
 *
 * Use:		Writes digits of %$\pi$% to the given array.  The algorithm
 *		is based on the Spigot algorithm by Stanley Rabinowitz and
 *		Stan Wagon, published in Amer.Math.Monthly, March 1995, with
 *		bug fixes by C. Haenel.  I then bodged it to output hex
 *		digits rather than decimal ones, and to leave off the initial
 *		`3'.
 *
 *		I've not analysed the algorithm very much.
 */

#define SPIGOT_WORDS (18 + 4 * 256ul)
#define SPIGOT_BITS 8
#define SPIGOT_RADIX (1ul << SPIGOT_BITS)
#define SPIGOT_BUFLEN (SPIGOT_WORDS * 32)

static void spigot(uint32 *buf, size_t n)
{
  uint32 acc = 0;
  int b = -1;
  unsigned a[SPIGOT_BUFLEN] = { 0 };
  uint32 p = 0;
  unsigned f = 0;
  unsigned max = 32 * n;
  size_t step = n / 60;

  fputs("[                                                             ]\r[",
	stderr);

#define EMIT(z) do {							\
  if (b == -1)								\
    b = 0;								\
  else {								\
    acc = (acc << SPIGOT_BITS) | (z);					\
    b += SPIGOT_BITS;							\
    if (b == 32) {							\
      *buf++ = acc;							\
      acc = 0;								\
      b = 0;								\
      n--;								\
      if (!n)								\
	goto done;							\
      if (n % step == 0)						\
	fputc('.', stderr);						\
    }									\
  }									\
} while (0)

  while (n) {
    uint32 q = 0;
    uint32 i;
    uint32 x = 0;
    uint32 k = max * 2 - 1;

    for (i = max; i; i--) {
      x = (b == -1 ? SPIGOT_RADIX * 2 : a[i - 1] << SPIGOT_BITS) + q * i;
      q = x / k;
      a[i - 1] = x - q * k;
      k -= 2;
    }

    k = x & (SPIGOT_RADIX - 1);
    if (k == SPIGOT_RADIX - 1)
      f++;
    else {
      EMIT(p + (x >> SPIGOT_BITS));
      if (f) {
	unsigned d = (x >= SPIGOT_RADIX ? 0 : SPIGOT_RADIX - 1);
	while (f) {
	  EMIT(d);
	  f--;
	}
      }
      p = k;
    }
  }

done:
  fputc('\n', stderr);

#undef EMIT
}

/* --- @main@ --- */

int main(void)
{
  uint32 dbuf[SPIGOT_WORDS];
  int i, j;
  uint32 *d = dbuf;

  spigot(d, SPIGOT_WORDS);

  fputs("\
/* -*-c-*-\n\
 *\n\
 * Blowfish initial key table [generated]\n\
 */\n\
\n\
#ifndef CATACOMB_BLOWFISH_TAB_H\n\
#define CATACOMB_BLOWFISH_TAB_H\n\
\n\
#define BLOWFISH_IKEY {							\\\n\
  { ", stdout);

  for (i = 0; i < 18; i++) {
    printf("0x%08x", *d++);
    if (i == 17)
      fputs(" },						\\\n\
									\\\n\
  { ", stdout);
    else if (i % 4 == 3)
      fputs(",			\\\n    ", stdout);
    else
      fputs(", ", stdout);
  }

  for (j = 0; j < 4; j++) {
    for (i = 0; i < 256; i++) {
    printf("0x%08x", *d++);
    if (i == 255) {
      if (j == 3)
	fputs(" }			\\\n}\n\n#endif\n", stdout);
      else
	fputs(" },			\\\n\
									\\\n\
  { ", stdout);
    } else if (i % 4 == 3)
      fputs(",			\\\n    ", stdout);
    else
      fputs(", ", stdout);
    }
  }

  if (fclose(stdout)) {
    fprintf(stderr, "error writing data\n");
    exit(EXIT_FAILURE);
  }
  return (0);
}

/*----- That's all, folks -------------------------------------------------*/