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 #ifdef QUIET
  62 #  define Q(x)
  63 #else
  64 #  define Q(x) x
  65 #endif
  66
  67 static void spigot(uint32 *buf, size_t n)
  68 {
  69   uint32 acc = 0;
  70   int b = -1;
  71   unsigned a[SPIGOT_BUFLEN] = { 0 };
  72   uint32 p = 0;
  73   unsigned f = 0;
  74   unsigned max = 32 * n;
  75   Q( size_t step = n / 60; )
  76
  77   Q( fputs("[                                                          ]\r[",
  78            stderr); )
  79
  80 #define EMIT(z) do {                                                    \
  81   if (b == -1)                                                          \
  82     b = 0;                                                              \
  83   else {                                                                \
  84     acc = (acc << SPIGOT_BITS) | (z);                                   \
  85     b += SPIGOT_BITS;                                                   \
  86     if (b == 32) {                                                      \
  87       *buf++ = acc;                                                     \
  88       acc = 0;                                                          \
  89       b = 0;                                                            \
  90       n--;                                                              \
  91       if (!n)                                                           \
  92         goto done;                                                      \
  93       Q( if (n % step == 0)                                             \
  94            fputc('.', stderr); )                                        \
  95     }                                                                   \
  96   }                                                                     \
  97 } while (0)
  98
  99   while (n) {
 100     uint32 q = 0;
 101     uint32 i;
 102     uint32 x = 0;
 103     uint32 k = max * 2 - 1;
 104
 105     for (i = max; i; i--) {
 106       x = (b == -1 ? SPIGOT_RADIX * 2 : a[i - 1] << SPIGOT_BITS) + q * i;
 107       q = x / k;
 108       a[i - 1] = x - q * k;
 109       k -= 2;
 110     }
 111
 112     k = x & (SPIGOT_RADIX - 1);
 113     if (k == SPIGOT_RADIX - 1)
 114       f++;
 115     else {
 116       EMIT(p + (x >> SPIGOT_BITS));
 117       if (f) {
 118         unsigned d = (x >= SPIGOT_RADIX ? 0 : SPIGOT_RADIX - 1);
 119         while (f) {
 120           EMIT(d);
 121           f--;
 122         }
 123       }
 124       p = k;
 125     }
 126   }
 127
 128 done:;
 129   Q( fputc('\n', stderr); )
 130
 131 #undef EMIT
 132 }
 133
 134 /* --- @main@ --- */
 135
 136 int main(void)
 137 {
 138   uint32 dbuf[SPIGOT_WORDS];
 139   int i, j;
 140   uint32 *d = dbuf;
 141
 142   spigot(d, SPIGOT_WORDS);
 143
 144   fputs("\
 145 /* -*-c-*-\n\
 146  *\n\
 147  * Blowfish initial key table [generated]\n\
 148  */\n\
 149 \n\
 150 #ifndef CATACOMB_BLOWFISH_TAB_H\n\
 151 #define CATACOMB_BLOWFISH_TAB_H\n\
 152 \n\
 153 #define BLOWFISH_IKEY {                                                 \\\n\
 154   { ", stdout);
 155
 156   for (i = 0; i < 18; i++) {
 157     printf("0x%08x", *d++);
 158     if (i == 17)
 159       fputs(" },                                                \\\n\
 160                                                                         \\\n\
 161   { ", stdout);
 162     else if (i % 4 == 3)
 163       fputs(",                  \\\n    ", stdout);
 164     else
 165       fputs(", ", stdout);
 166   }
 167
 168   for (j = 0; j < 4; j++) {
 169     for (i = 0; i < 256; i++) {
 170     printf("0x%08x", *d++);
 171     if (i == 255) {
 172       if (j == 3)
 173         fputs(" }                       \\\n}\n\n#endif\n", stdout);
 174       else
 175         fputs(" },                      \\\n\
 176                                                                         \\\n\
 177   { ", stdout);
 178     } else if (i % 4 == 3)
 179       fputs(",                  \\\n    ", stdout);
 180     else
 181       fputs(", ", stdout);
 182     }
 183   }
 184
 185   if (fclose(stdout)) {
 186     fprintf(stderr, "error writing data\n");
 187     exit(EXIT_FAILURE);
 188   }
 189   return (0);
 190 }
 191
 192 /*----- That's all, folks -------------------------------------------------*/