chiark - git - mdw - catacomb/blob - blowfish-mktab.c

   1 /* -*-c-*-
   2  *
   3  * $Id: blowfish-mktab.c,v 1.3 2004/04/08 01:36:15 mdw Exp $
   4  *
   5  * Build Blowfish key table
   6  *
   7  * (c) 2000 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34
  35 #include <mLib/bits.h>
  36
  37 /*----- Main code ---------------------------------------------------------*/
  38
  39 /* --- @spigot@ --- *
  40  *
  41  * Arguments:   @uint32 *buf@ = pointer to the output buffer
  42  *              @size_t n@ = number of output digits wanted
  43  *
  44  * Returns:     ---
  45  *
  46  * Use:         Writes digits of %$\pi$% to the given array.  The algorithm
  47  *              is based on the Spigot algorithm by Stanley Rabinowitz and
  48  *              Stan Wagon, published in Amer.Math.Monthly, March 1995, with
  49  *              bug fixes by C. Haenel.  I then bodged it to output hex
  50  *              digits rather than decimal ones, and to leave off the initial
  51  *              `3'.
  52  *
  53  *              I've not analysed the algorithm very much.
  54  */
  55
  56 #define SPIGOT_WORDS (18 + 4 * 256ul)
  57 #define SPIGOT_BITS 8
  58 #define SPIGOT_RADIX (1ul << SPIGOT_BITS)
  59 #define SPIGOT_BUFLEN (SPIGOT_WORDS * 32)
  60
  61 static void spigot(uint32 *buf, size_t n)
  62 {
  63   uint32 acc = 0;
  64   int b = -1;
  65   unsigned a[SPIGOT_BUFLEN] = { 0 };
  66   uint32 p = 0;
  67   unsigned f = 0;
  68   unsigned max = 32 * n;
  69   size_t step = n / 60;
  70
  71   fputs("[                                                             ]\r[",
  72         stderr);
  73
  74 #define EMIT(z) do {                                                    \
  75   if (b == -1)                                                          \
  76     b = 0;                                                              \
  77   else {                                                                \
  78     acc = (acc << SPIGOT_BITS) | (z);                                   \
  79     b += SPIGOT_BITS;                                                   \
  80     if (b == 32) {                                                      \
  81       *buf++ = acc;                                                     \
  82       acc = 0;                                                          \
  83       b = 0;                                                            \
  84       n--;                                                              \
  85       if (!n)                                                           \
  86         goto done;                                                      \
  87       if (n % step == 0)                                                \
  88         fputc('.', stderr);                                             \
  89     }                                                                   \
  90   }                                                                     \
  91 } while (0)
  92
  93   while (n) {
  94     uint32 q = 0;
  95     uint32 i;
  96     uint32 x = 0;
  97     uint32 k = max * 2 - 1;
  98
  99     for (i = max; i; i--) {
 100       x = (b == -1 ? SPIGOT_RADIX * 2 : a[i - 1] << SPIGOT_BITS) + q * i;
 101       q = x / k;
 102       a[i - 1] = x - q * k;
 103       k -= 2;
 104     }
 105
 106     k = x & (SPIGOT_RADIX - 1);
 107     if (k == SPIGOT_RADIX - 1)
 108       f++;
 109     else {
 110       EMIT(p + (x >> SPIGOT_BITS));
 111       if (f) {
 112         unsigned d = (x >= SPIGOT_RADIX ? 0 : SPIGOT_RADIX - 1);
 113         while (f) {
 114           EMIT(d);
 115           f--;
 116         }
 117       }
 118       p = k;
 119     }
 120   }
 121
 122 done:
 123   fputc('\n', stderr);
 124
 125 #undef EMIT
 126 }
 127
 128 /* --- @main@ --- */
 129
 130 int main(void)
 131 {
 132   uint32 dbuf[SPIGOT_WORDS];
 133   int i, j;
 134   uint32 *d = dbuf;
 135
 136   spigot(d, SPIGOT_WORDS);
 137
 138   fputs("\
 139 /* -*-c-*-\n\
 140  *\n\
 141  * Blowfish initial key table [generated]\n\
 142  */\n\
 143 \n\
 144 #ifndef CATACOMB_BLOWFISH_TAB_H\n\
 145 #define CATACOMB_BLOWFISH_TAB_H\n\
 146 \n\
 147 #define BLOWFISH_IKEY {                                                 \\\n\
 148   { ", stdout);
 149
 150   for (i = 0; i < 18; i++) {
 151     printf("0x%08x", *d++);
 152     if (i == 17)
 153       fputs(" },                                                \\\n\
 154                                                                         \\\n\
 155   { ", stdout);
 156     else if (i % 4 == 3)
 157       fputs(",                  \\\n    ", stdout);
 158     else
 159       fputs(", ", stdout);
 160   }
 161
 162   for (j = 0; j < 4; j++) {
 163     for (i = 0; i < 256; i++) {
 164     printf("0x%08x", *d++);
 165     if (i == 255) {
 166       if (j == 3)
 167         fputs(" }                       \\\n}\n\n#endif\n", stdout);
 168       else
 169         fputs(" },                      \\\n\
 170                                                                         \\\n\
 171   { ", stdout);
 172     } else if (i % 4 == 3)
 173       fputs(",                  \\\n    ", stdout);
 174     else
 175       fputs(", ", stdout);
 176     }
 177   }
 178
 179   if (fclose(stdout)) {
 180     fprintf(stderr, "error writing data\n");
 181     exit(EXIT_FAILURE);
 182   }
 183   return (0);
 184 }
 185
 186 /*----- That's all, folks -------------------------------------------------*/