Generate precomputed tables as sources in `precomps/'.

[u/mdw/catacomb] / symm / des-mktab.c

/* -*-c-*-
 *
 * Build combined S-P tables for DES
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

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

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

#include <mLib/bits.h>

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

/* --- S boxes --- */

static const char s[8][4][16] = {

  /* --- S1 --- */

  { { 14,  4, 13,  1,  2, 15, 11,  8,  3, 10,  6, 12,  5,  9,  0,  7 },
    {  0, 15,  7,  4, 14,  2, 13,  1, 10,  6, 12, 11,  9,  5,  3,  8 },
    {  4,  1, 14,  8, 13,  6,  2, 11, 15, 12,  9,  7,  3, 10,  5,  0 },
    { 15, 12,  8,  2,  4,  9,  1,  7,  5, 11,  3, 14, 10,  0,  6, 13 } },

  /* --- S2 --- */

  { { 15,  1,  8, 14,  6, 11,  3,  4,  9,  7,  2, 13, 12,  0,  5, 10 },
    {  3, 13,  4,  7, 15,  2,  8, 14, 12,  0,  1, 10,  6,  9, 11,  5 },
    {  0, 14,  7, 11, 10,  4, 13,  1,  5,  8, 12,  6,  9,  3,  2, 15 },
    { 13,  8, 10,  1,  3, 15,  4,  2, 11,  6,  7, 12,  0,  5, 14,  9 } },

  /* --- S3 --- */

  { { 10,  0,  9, 14,  6,  3, 15,  5,  1, 13, 12,  7, 11,  4,  2,  8 },
    { 13,  7,  0,  9,  3,  4,  6, 10,  2,  8,  5, 14, 12, 11, 15,  1 },
    { 13,  6,  4,  9,  8, 15,  3,  0, 11,  1,  2, 12,  5, 10, 14,  7 },
    {  1, 10, 13,  0,  6,  9,  8,  7,  4, 15, 14,  3, 11,  5,  2, 12 } },

  /* --- S4 --- */

  { {  7, 13, 14,  3,  0,  6,  9, 10,  1,  2,  8,  5, 11, 12,  4, 15 },
    { 13,  8, 11,  5,  6, 15,  0,  3,  4,  7,  2, 12,  1, 10, 14,  9 },
    { 10,  6,  9,  0, 12, 11,  7, 13, 15,  1,  3, 14,  5,  2,  8,  4 },
    {  3, 15,  0,  6, 10,  1, 13,  8,  9,  4,  5, 11, 12,  7,  2, 14 } },

  /* --- S5 --- */

  { {  2, 12,  4,  1,  7, 10, 11,  6,  8,  5,  3, 15, 13,  0, 14,  9 },
    { 14, 11,  2, 12,  4,  7, 13,  1,  5,  0, 15, 10,  3,  9,  8,  6 },
    {  4,  2,  1, 11, 10, 13,  7,  8, 15,  9, 12,  5,  6,  3,  0, 14 },
    { 11,  8, 12,  7,  1, 14,  2, 13,  6, 15,  0,  9, 10,  4,  5,  3 } },

  /* --- S6 --- */

  { { 12,  1, 10, 15,  9,  2,  6,  8,  0, 13,  3,  4, 14,  7,  5, 11 },
    { 10, 15,  4,  2,  7, 12,  9,  5,  6,  1, 13, 14,  0, 11,  3,  8 },
    {  9, 14, 15,  5,  2,  8, 12,  3,  7,  0,  4, 10,  1, 13, 11,  6 },
    {  4,  3,  2, 12,  9,  5, 15, 10, 11, 14,  1,  7,  6,  0,  8, 13 } },

  /* --- S7 --- */

  { {  4, 11,  2, 14, 15,  0,  8, 13,  3, 12,  9,  7,  5, 10,  6,  1 },
    { 13,  0, 11,  7,  4,  9,  1, 10, 14,  3,  5, 12,  2, 15,  8,  6 },
    {  1,  4, 11, 13, 12,  3,  7, 14, 10, 15,  6,  8,  0,  5,  9,  2 },
    {  6, 11, 13,  8,  1,  4, 10,  7,  9,  5,  0, 15, 14,  2,  3, 12 } },

  /* --- S8 --- */

  { { 13,  2,  8,  4,  6, 15, 11,  1, 10,  9,  3, 14,  5,  0, 12,  7 },
    {  1, 15, 13,  8, 10,  3,  7,  4, 12,  5,  6, 11,  0, 14,  9,  2 },
    {  7, 11,  4,  1,  9, 12, 14,  2,  0,  6, 10, 13, 15,  3,  5,  8 },
    {  2,  1, 14,  7,  4, 10,  8, 13, 15, 12,  9,  0,  3,  5,  6, 11 } }
};

/* --- P table --- */

static char p[32] = {
  16,  7, 20, 21, 29, 12, 28, 17,  1, 15, 23, 26,  5, 18, 31, 10,
   2,  8, 24, 14, 32, 27,  3,  9, 19, 13, 30,  6, 22, 11,  4, 25
};

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

/* --- @unique@ --- *
 *
 * Arguments:	@const char *t@ = pointer to table
 *		@int base@ = base of the data
 *		@int sz@ = number of elements
 *		@const char *name@ = name of this table
 *		@...@ = things to fill in
 *
 * Returns:	Zero if it failed, nonzero if it didn't.
 *
 * Use:		Validates a table.  All the elements must be in range and
 *		unique.
 */

static int unique(const char *t, int base, int sz, const char *name, ...)
{
  char u[32];
  char nbuf[128];
  int i;
  int ok = 1;

  {
    va_list ap;
    va_start(ap, name);
    vsprintf(nbuf, name, ap);
    va_end(ap);
  }

  if (sz > sizeof(u)) {
    fprintf(stderr, "internal error: table `%s' too large\n", nbuf);
    exit(EXIT_FAILURE);
  }
  memset(u, 0, sizeof(u));
  for (i = 0; i < sz; i++) {
    int x = t[i] - base;
    if (x >= sz) {
      fprintf(stderr, "validation error: %i too big (index %i) in %s\n",
	      x + base, i, nbuf);
      ok = 0;
    } else if (u[x]) {
      fprintf(stderr, "validation error: duplicate %i (index %i) in %s\n",
	      x + base, i, nbuf);
      ok = 0;
    }
    u[x] = 1;
  }
  for (i = 0; i < sz; i++) {
    if (!u[i]) {
      fprintf(stderr, "validation error: missing %i in %s\n",
	      i + base, nbuf);
      ok = 0;
    }
  }

  return (ok);
}

/* --- @validate@ --- *
 *
 * Arguments:	---
 *
 * Returns:	Only if everything's OK.
 *
 * Use:		Validates the tables.  A bit.  Not much at all...
 */

static void validate(void)
{
  int i, j;
  int ok = 1;

  for (i = 0; i < 8; i++) for (j = 0; j < 4; j++)
    if (!unique(s[i][j], 0, 16, "sbox %i, row %i", i, j)) ok = 0;
  if (!unique(p, 1, 32, "p")) ok = 0;
  if (!ok)
    exit(EXIT_FAILURE);
}

/* --- @permute@ --- *
 *
 * Arguments:	@unsigned long x@ = value to permute
 *
 * Returns:	Permuted version of @x@.
 *
 * Use:		Permutes a number.  The result is the input value after
 *		having been spewed through the @P@ permutation, and then
 *		(and this is important) rotated left one place.
 */

static unsigned long permute(unsigned long x)
{
  unsigned long y = 0;
  unsigned i;

  for (i = 0; i < 32; i++) {
    if (x & (1 << (32 - p[i])))
      y |= (1 << (31 - i));
  }
  return (ROL32(y, 1));
}

/* --- @mangle@ --- *
 *
 * Arguments:	@const char s[4][16]@ = an s-box
 *		@unsigned long ss[64]@ = output buffer
 *		@int bitoff@ = bit offset to use
 *
 * Returns:	---
 *
 * Use:		Mangles the s-box.  Specifically, the bizarre indexing is
 *		transformed into something sensible, and the result is
 *		permuted according to the @p@ table.
 */

static void mangle(const char s[4][16], unsigned long *ss, int bitoff)
{
  unsigned i;
  for (i = 0; i < 64; i++) {
    unsigned row = ((i & 0x20) >> 4) | (i & 0x01);
    unsigned col = (i & 0x1e) >> 1;
    ss[i] = permute(s[row][col] << bitoff);
  }
}

/* --- @main@ --- */

int main(void)
{
  int i, j;
  unsigned long ss[64];
  const char *sep;

  validate();

  fputs("\
/* -*-c-*-\n\
 *\n\
 * DES tables [generated]\n\
 */\n\
\n\
#include \"des-base.h\"\n\
\n\
const uint32 des_sp[8][64] = {\n\
", stdout);
  for (i = 0; i < 8; i++) {
    mangle(s[i], ss, 28 - 4 * i);
    printf("\n  /* --- SP[%i] --- */\n\n", i);
    sep = "  { ";
    for (j = 0; j < 64; j++) {
      printf("%s0x%08lx", sep, ss[j]);
      if (j % 4 == 3)
	sep = ",\n    ";
      else
	sep = ", ";
    }
    printf(" }%s\n", i == 7 ? "" : ",");
  }
  fputs("};\n", stdout);

  if (fclose(stdout)) {
    fprintf(stderr, "error writing data\n");
    exit(EXIT_FAILURE);
  }

  return (0);
}

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