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

   1 /* -*-c-*-
   2  *
   3  * $Id: diffan.c,v 1.3 2000/07/02 15:21:20 mdw Exp $
   4  *
   5  * Differential analysis of matrix multiplication
   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: diffan.c,v $
  52  * Revision 1.3  2000/07/02 15:21:20  mdw
  53  * Fix licence text.
  54  *
  55  * Revision 1.2  2000/05/28 00:39:52  mdw
  56  * Bad bug makes all previous testing worthless.
  57  *
  58  * Revision 1.1  2000/05/21 11:28:30  mdw
  59  * Initial check-in.
  60  *
  61  */
  62
  63 /*----- Header files ------------------------------------------------------*/
  64
  65 #include <stdio.h>
  66 #include <stdlib.h>
  67
  68 #include "bits.h"
  69 #include "sym.h"
  70 #include "fibrand.h"
  71 #include "matrix.h"
  72 #include "storin-tab.h"
  73
  74 /*----- The constant matrix -----------------------------------------------*/
  75
  76 static const uint24 m[] = STORIN_M;
  77
  78 /*----- Magic numbers -----------------------------------------------------*/
  79
  80 #define PROBES 8192
  81 #define EXHAUST 4
  82
  83 /*----- Static variables --------------------------------------------------*/
  84
  85 static fibrand r;
  86
  87 /*----- Main code ---------------------------------------------------------*/
  88
  89 typedef struct {
  90   sym_base b;
  91   unsigned n;
  92 } diff;
  93
  94 static void probe(uint24 *delta)
  95 {
  96   unsigned i, j;
  97   unsigned max = 0;
  98   uint24 mout[4];
  99   sym_table t;
 100
 101   sym_create(&t);
 102
 103   for (i = 0; i < PROBES; i++) {
 104     uint24 x[4], y[4];
 105     uint24 xi[4], yi[4];
 106     uint24 dd[4];
 107     octet db[12];
 108     diff *p;
 109     unsigned c;
 110
 111     for (j = 0; j < 4; j++) {
 112       x[j] = U24(fibrand_step(&r));
 113       y[j] = x[j] ^ delta[j];
 114     }
 115
 116     matmul(xi, m, x, 4, 4, 1);
 117     matmul(yi, m, y, 4, 4, 1);
 118
 119     for (j = 0; j < 4; j++)
 120       dd[j] = xi[j] ^ yi[j];
 121
 122     STORE24(db + 0, dd[0]);
 123     STORE24(db + 3, dd[1]);
 124     STORE24(db + 6, dd[2]);
 125     STORE24(db + 9, dd[3]);
 126
 127     p = sym_find(&t, (char *)db, 12, sizeof(*p), &c);
 128     if (!c)
 129       p->n = 1;
 130     else
 131       p->n++;
 132     if (p->n > max) {
 133       max = p->n;
 134       for (j = 0; j < 4; j++)
 135         mout[j] = dd[j];
 136     }
 137   }
 138
 139   sym_destroy(&t);
 140
 141   if (max > 1) {
 142     printf("%06x %06x %06x %06x -> %06x %06x %06x %06x: %u\n",
 143            delta[0], delta[1], delta[2], delta[3],
 144            mout[0], mout[1], mout[2], mout[3], max);
 145   }
 146 }
 147
 148 static void rdiff(uint24 *delta, unsigned i, unsigned n)
 149 {
 150   if (!n) {
 151     probe(delta);
 152     return;
 153   }
 154   for (; i < 96; i++) {
 155     uint24 *dd = delta + i / 24;
 156     uint24 m = 1 << (i % 24);
 157     *dd ^= m;
 158     rdiff(delta, i + 1, n - 1);
 159     *dd ^= m;
 160   }
 161 }
 162
 163 static void bitdiffs(unsigned n)
 164 {
 165   uint24 delta[4] = { 0 };
 166   rdiff(delta, 0, n);
 167   probe(delta);
 168 }
 169
 170 int main(void)
 171 {
 172   unsigned i, j;
 173   uint24 delta[4];
 174
 175   fibrand_lcseed(&r, 0);
 176
 177   for (i = 1; i <= EXHAUST; i++)
 178     bitdiffs(i);
 179
 180   printf("*** ok, trying random probing\n");
 181
 182   for (;;) {
 183     for (j = 0; j < 4; j++)
 184       delta[j] = U24(fibrand_step(&r));
 185     probe(delta);
 186   }
 187
 188   return (0);
 189 }
 190
 191 /*----- That's all, folks -------------------------------------------------*/