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

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