chiark - git - mdw - storin/blob - sac.c

   1 /* -*-c-*-
   2  *
   3  * $Id: sac.c,v 1.2 2000/07/02 15:21:20 mdw Exp $
   4  *
   5  * Testing for strict avalanche
   6  *
   7  * (c) 2000 Mark Wooding
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * Copyright (c) 2000 Mark Wooding
  13  * All rights reserved.
  14  *
  15  * Redistribution and use in source and binary forms, with or without
  16  * modification, are permitted provided that the following conditions are
  17  * met:
  18  *
  19  * 1. Redistributions of source code must retain the above copyright
  20  *    notice, this list of conditions and the following disclaimer.
  21  *
  22  * 2, Redistributions in binary form must reproduce the above copyright
  23  *    notice, this list of conditions and the following disclaimer in the
  24  *    documentation and/or other materials provided with the distribution.
  25  *
  26  * 3. The name of the authors may not be used to endorse or promote
  27  *    products derived from this software without specific prior written
  28  *    permission.
  29  *
  30  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
  31  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  32  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN
  33  * NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
  34  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  35  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  36  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  37  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  38  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  39  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  40  * POSSIBILITY OF SUCH DAMAGE.
  41  *
  42  * Instead of accepting the above terms, you may redistribute and/or modify
  43  * this software under the terms of either the GNU General Public License,
  44  * or the GNU Library General Public License, published by the Free
  45  * Software Foundation; either version 2 of the License, or (at your
  46  * option) any later version.
  47  */
  48
  49 /*----- Revision history --------------------------------------------------*
  50  *
  51  * $Log: sac.c,v $
  52  * Revision 1.2  2000/07/02 15:21:20  mdw
  53  * Fix licence text.
  54  *
  55  * Revision 1.1  2000/05/21 11:28:30  mdw
  56  * Initial check-in.
  57  *
  58  */
  59
  60 /*----- Header files ------------------------------------------------------*/
  61
  62 #include <math.h>
  63 #include <stdio.h>
  64 #include <stdlib.h>
  65
  66 #include "bits.h"
  67
  68 #include "fibrand.h"
  69 #include "matrix.h"
  70 #include "storin-tab.h"
  71
  72 /*----- Static variables --------------------------------------------------*/
  73
  74 static fibrand r;
  75
  76 /*----- The constant matrix -----------------------------------------------*/
  77
  78 static const uint24 m[] = STORIN_M;
  79
  80 /*----- Magic numbers -----------------------------------------------------*/
  81
  82 #define PROBES 16384
  83 #define ROUNDS 3
  84 #define ROT(x) ((x) ^ ((x) >> 12))
  85 /* #define ROT(x) ROL24(x, 7) */
  86
  87 /*----- Main code ---------------------------------------------------------*/
  88
  89 static octet w[256];
  90
  91 #define HAMWEIGHT(x) (w[U8((x) >> 16)] + w[U8((x) >> 8)] + w[U8(x)])
  92
  93 static void haminit(void) {
  94   unsigned i;
  95   for (i = 0; i < 256; i++) {
  96     unsigned ww = 0;
  97     unsigned j;
  98     for (j = 0; j < 8; j++) {
  99       if (i & (1 << j))
 100         ww++;
 101     }
 102     w[i] = ww;
 103   }
 104 }
 105
 106 static void eblk(uint24 *x)
 107 {
 108   uint24 t[4];
 109   unsigned i, j;
 110
 111   for (i = 0; i < ROUNDS; i++) {
 112     /* No key mixing */
 113     matmul(t, m, x, 4, 4, 1);
 114     for (j = 0; j < 4; j++)
 115       x[j] = ROT(t[j]);
 116   }
 117 }
 118
 119 typedef struct stats {
 120   double sx;
 121   double sx2;
 122   double n;
 123 } stats;
 124
 125 static void probe(unsigned bit, uint24 *delta, struct stats *ps)
 126 {
 127   uint24 x[4], y[4];
 128   unsigned i, j;
 129   struct stats s = { 0, 0, 0 };
 130
 131   for (i = 0; i < PROBES; i++) {
 132     unsigned h;
 133     for (j = 0; j < 4; j++) {
 134       x[j] = U24(fibrand_step(&r));
 135       y[j] = x[j] ^ delta[j];
 136     }
 137     eblk(x);
 138     eblk(y);
 139     h = 0;
 140     for (j = 0; j < 4; j++) {
 141       uint24 ww = x[j] ^ y[j];
 142       h += HAMWEIGHT(ww);
 143     }
 144 /*     printf("%06x %06x %06x %06x -> %06x %06x %06x %06x\n", */
 145 /*         delta[0], delta[1], delta[2], delta[3], */
 146 /*         x[0] ^ y[0], x[1] ^ y[1], x[2] ^ y[2], x[3] ^ y[3]); */
 147     s.sx += h; ps->sx += h;
 148     s.sx2 += h * h; ps->sx2 += h * h;
 149     s.n++; ps->n++;
 150   }
 151
 152   {
 153     double mean = s.sx / s.n;
 154     double var = s.sx2 / s.n - mean * mean;
 155     printf("bit %u: mean = %g, sd = %g\n", bit, mean, sqrt(var));
 156   }
 157 }
 158
 159 int main(void)
 160 {
 161   uint24 delta[4] = { 0 };
 162   unsigned i;
 163   struct stats s = { 0, 0, 0 };
 164   double mean, var;
 165
 166   haminit();
 167   fibrand_lcseed(&r, 0);
 168
 169   for (i = 0; i < 96; i++) {
 170     uint24 *dd = delta + i / 24;
 171     uint24 m = 1 << (i % 24);
 172     *dd ^= m;
 173     probe(i, delta, &s);
 174     *dd ^= m;
 175   }
 176
 177   mean = s.sx / s.n;
 178   var = s.sx2 / s.n - mean * mean;
 179   printf("\nsummary: mean = %g, sd = %g\n", mean, sqrt(var));
 180
 181   return (0);
 182 }
 183
 184 /*----- That's all, folks -------------------------------------------------*/