Improve analysis section.

[storin] / diffan.c

/* -*-c-*-
 *
 * $Id: diffan.c,v 1.1 2000/05/21 11:28:30 mdw Exp $
 *
 * Differential analysis of matrix multiplication
 *
 * (c) 2000 Mark Wooding
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * Copyright (c) 2000 Mark Wooding
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 
 * 2, Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * 3. The name of the authors may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 * 
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN
 * NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 * 
 * Instead of accepting the above terms, you may redistribute and/or modify
 * this software under the terms of either the GNU General Public License,
 * or the GNU Library General Public License, published by the Free
 * Software Foundation; either version 2 of the License, or (at your
 * option) any later version.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: diffan.c,v $
 * Revision 1.1  2000/05/21 11:28:30  mdw
 * Initial check-in.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#include "bits.h"
#include "sym.h"
#include "fibrand.h"
#include "matrix.h"
#include "storin-tab.h"

/*----- The constant matrix -----------------------------------------------*/

static const uint24 m[] = STORIN_M;

/*----- Magic numbers -----------------------------------------------------*/

#define PROBES 8192
#define EXHAUST 4

/*----- Static variables --------------------------------------------------*/

static fibrand r;

/*----- Main code ---------------------------------------------------------*/

typedef struct {
  sym_base b;
  unsigned n;
} diff;

static void probe(uint24 *delta)
{
  unsigned i, j;
  unsigned max = 0;
  uint24 mout[4];
  sym_table t;

  sym_create(&t);

  for (i = 0; i < PROBES; i++) {
    uint24 x[4], y[4];
    uint24 xi[4], yi[4];
    uint24 dd[4];
    octet db[12];
    diff *p;
    unsigned c;

    for (j = 0; j < 4; j++) {
      x[j] = U24(fibrand_step(&r));
      y[j] = x[j] & delta[j];
    }

    matmul(xi, m, x, 4, 4, 1);
    matmul(yi, m, y, 4, 4, 1);

    for (j = 0; j < 4; j++)
      dd[j] = xi[j] ^ yi[j];

    STORE24(db + 0, dd[0]);
    STORE24(db + 3, dd[1]);
    STORE24(db + 6, dd[2]);
    STORE24(db + 9, dd[3]);

    p = sym_find(&t, (char *)db, 12, sizeof(*p), &c);
    if (!c)
      p->n = 1;
    else
      p->n++;
    if (p->n > max) {
      max = p->n;
      for (j = 0; j < 4; j++)
	mout[j] = dd[j];
    }
  }

  sym_destroy(&t);

  if (max > 1) {
    printf("%06x %06x %06x %06x -> %06x %06x %06x %06x: %u\n",
	   delta[0], delta[1], delta[2], delta[3],
	   mout[0], mout[1], mout[2], mout[3], max);
  }
}

static void rdiff(uint24 *delta, unsigned i, unsigned n)
{
  if (!n) {
    probe(delta);
    return;
  }
  for (; i < 96; i++) {
    uint24 *dd = delta + i / 24;
    uint24 m = 1 << (i % 24);
    *dd ^= m;
    rdiff(delta, i + 1, n - 1);
    *dd ^= m;
  }
}

static void bitdiffs(unsigned n)
{
  uint24 delta[4] = { 0 };
  rdiff(delta, 0, n);
  probe(delta);
}

int main(void)
{
  unsigned i, j;
  uint24 delta[4];

  fibrand_lcseed(&r, 0);

  for (i = 1; i <= EXHAUST; i++)
    bitdiffs(i);

  printf("*** ok, trying random probing\n");

  for (;;) {
    for (j = 0; j < 4; j++)
      delta[j] = U24(fibrand_step(&r));
    probe(delta);
  }

  return (0);
}

/*----- That's all, folks -------------------------------------------------*/