NetNews Usenet Archive 1992 #30/NN_1992_30.iso/spool/sci/crypt/5742

Internet Message Format | 1992-12-16 | 7.2 KB

Path: sparky!uunet!noc.near.net!transfer.stratus.com!ellisun.sw.stratus.com!cme
From: [e-mail] (Carl Ellison)
Newsgroups: sci.crypt
Subject: reposting of tran
Date: 16 Dec 1992 18:39:36 GMT
Organization: Stratus Computer, Software Engineering
Lines: 251
Distribution: world
Message-ID: <[e-mail]>
NNTP-Posting-Host: ellisun.sw.stratus.com

I have made reference to a UNIX program called tran, several times, and was
finally asked where to find it.  It had been posted on sci.crypt
a while ago.  I've since modified it a little and decided to re-post it.
The original posting was by [e-mail] (William Setzer).
Many thanks to him for this code.

--Carl

P.S.  To try it, unpack this shar file into a blank directory then
use the command

    make test

(also available,  "make clean", "make all", "make tran").

---- Cut Here and unpack ----
#!/bin/sh
# shar:    Shell Archiver  (v1.22)
#
#    Run the following text with /bin/sh to create:
#      Makefile
#      foo
#      rnd.c
#      tran.c
#
if test -f Makefile; then echo "File Makefile exists"; else
echo "x - extracting Makefile (Text)"
sed 's/^X//' << 'SHAR_EOF' > Makefile &&
Xall: tran
X
Xtran: tran.c rnd.c
X    cc -o tran -O rnd.c tran.c
X
Xtest: tmp all
X    tran < tmp > tmpo ; more tmpo ; mv tmpo tmp
X
Xtmp: foo
X    cp foo tmp
X
Xclean:
X    rm -f tmp tmpo tran tran.o rnd.o
SHAR_EOF
chmod 0644 Makefile || echo "restore of Makefile fails"
set `wc -c Makefile`;Sum=$1
if test "$Sum" != "182"
then echo original size 182, current size $Sum;fi
fi
if test -f foo; then echo "File foo exists"; else
echo "x - extracting foo (Text)"
sed 's/^X//' << 'SHAR_EOF' > foo &&
Xabcdefghijklmnopqrstuvwxyz0123456789-!@#$%^&*()_+[]{}'"`~;:,.<>/?|
SHAR_EOF
chmod 0664 foo || echo "restore of foo fails"
set `wc -c foo`;Sum=$1
if test "$Sum" != "67"
then echo original size 67, current size $Sum;fi
fi
if test -f rnd.c; then echo "File rnd.c exists"; else
echo "x - extracting rnd.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > rnd.c &&
X/* source/rnd.c: random number generator
X
X   Copyright (c) 1989-91 James E. Wilson
X
X   This software may be copied and distributed for educational, research, and
X   not for profit purposes provided that this copyright and statement are
X   included in all such copies. */
X
X/* This routine is straight out of the umoria5.3.1 distribution, except
X   that I hacked out the moria-specific stuff.  -WPS- */
X
X/* Define this to compile as a standalone test */
X
X/* This alg uses a prime modulus multiplicative congruential generator
X   (PMMLCG), also known as a Lehmer Grammer, which satisfies the following
X   properties
X
X   (i)     modulus: m - a large prime integer
X   (ii)     multiplier: a - an integer in the range 2, 3, ..., m - 1
X   (iii) z[n+1] = f(z[n]), for n = 1, 2, ...
X   (iv)     f(z) = az mod m
X   (v)     u[n] = z[n] / m, for n = 1, 2, ...
X
X   The sequence of z's must be initialized by choosing an initial seed
X   z[1] from the range 1, 2, ..., m - 1.  The sequence of z's is a pseudo-
X   random sequence drawn without replacement from the set 1, 2, ..., m - 1.
X   The u's form a psuedo-random sequence of real numbers between (but not
X   including) 0 and 1.
X
X   Schrage's method is used to compute the sequence of z's.
X   Let m = aq + r, where q = m div a, and r = m mod a.
X   Then f(z) = az mod m = az - m * (az div m) =
X         = gamma(z) + m * delta(z)
X   Where gamma(z) = a(z mod q) - r(z div q)
X   and     delta(z) = (z div q) - (az div m)
X
X   If r < q, then for all z in 1, 2, ..., m - 1:
X   (1) delta(z) is either 0 or 1
X   (2) both a(z mod q) and r(z div q) are in 0, 1, ..., m - 1
X   (3) absolute value of gamma(z) <= m - 1
X   (4) delta(z) = 1 iff gamma(z) < 0
X
X   Hence each value of z can be computed exactly without overflow as long
X   as m can be represented as an integer.
X */
X
X/* a good random number generator, correct on any machine with 32 bit
X   integers, this algorithm is from:
X
XStephen K. Park and Keith W. Miller, "Random Number Generators:
X    Good ones are hard to find", Communications of the ACM, October 1988,
X    vol 31, number 10, pp. 1192-1201.
X
X   If this algorithm is implemented correctly, then if z[1] = 1, then
X   z[10001] will equal 1043618065
X
X   Has a full period of 2^31 - 1.
X   Returns integers in the range 1 to 2^31-1.
X */
X
X#define RNG_M 2147483647L  /* m = 2^31 - 1 */
X#define RNG_A 16807L
X#define RNG_Q 127773L       /* m div a */
X#define RNG_R 2836L       /* m mod a */
X
X/* 32 bit seed */
Xstatic long rnd_seed;
X
Xvoid set_rnd_seed (seedval)
Xlong seedval;
X{
X  /* set seed to value between 1 and m-1 */
X
X  rnd_seed = (seedval % (RNG_M - 1)) + 1;
X}
X
X/* returns a pseudo-random number from set 1, 2, ..., RNG_M - 1 */
Xlong rnd()
X{
X  register long low, high, test;
X
X  high = rnd_seed / RNG_Q;
X  low = rnd_seed % RNG_Q;
X  test = RNG_A * low - RNG_R * high;
X  if (test > 0)
X    rnd_seed = test;
X  else
X    rnd_seed = test + RNG_M;
X  return rnd_seed;
X}
SHAR_EOF
chmod 0644 rnd.c || echo "restore of rnd.c fails"
set `wc -c rnd.c`;Sum=$1
if test "$Sum" != "2872"
then echo original size 2872, current size $Sum;fi
fi
if test -f tran.c; then echo "File tran.c exists"; else
echo "x - extracting tran.c (Text)"
sed 's/^X//' << 'SHAR_EOF' > tran.c &&
X/* modified from the original posting, by Carl Ellison, to remove */
X/* the password and therefore keep this from being an encryption program */
X/* The original code was written by [e-mail] (William Setzer) */
X
X#include <stdio.h>
X
Xextern void set_rnd_seed();
Xextern long rnd();
X
X#define BLOCKSIZE 8192
X
Xlong  perm[BLOCKSIZE];
Xchar buf[BLOCKSIZE];
X
XFILE *my_fopen(file, type)
Xchar *file, *type;
X{
X  FILE *fp;
X
X  if (fp = fopen(file, type))
X    return fp;
X  (void) fprintf(stderr, "Can't open '%s'\n", file);
X  exit(1);
X}
X
Xmain(argc, argv)
Xlong argc;
Xchar **argv;
X{
X  register long i, len;
X  register FILE *infp, *outfp;
X  long savlen, pos, key;
X  char tmp;
X
X  infp  = (argc > 1) ? my_fopen(argv[1], "r") : stdin;
X  outfp = (argc > 2) ? my_fopen(argv[2], "w") : stdout;
X
X  len = fread(buf, 1, BLOCKSIZE, infp);
X  key = lstr2int(buf,len);
X  set_rnd_seed(key);
X
X  do {
X    savlen = len;
X
X    for (i = 0; i < len; i++)
X      perm[i] = i;
X
X#define swap(A,B)  tmp = A; A = B; B = tmp;
X
X    while (len > 1)
X      {
X    pos = 1 + rnd() % (len - 1);
X    swap( buf[perm[0]], buf[perm[pos]] );
X
X    perm[0]   = perm[(pos == len - 2) ? len - 1 : len - 2];
X    perm[pos] = perm[len - 1];
X    len -= 2;
X      }
X    fwrite(buf, 1, savlen, outfp);
X  } while (len = fread(buf, 1, BLOCKSIZE, infp));
X}
X
X/* Make an integer out of a string.  Do a poor job of it.
X * Note that since this function is called on a block of transposed
X * text and used to construct an "rng key", it mustn't be sensitive
X * to the position of characters  in `str'.
X */
Xlong lstr2int(str,len)
Xchar *str;
Xlong len;
X{
X  long sum = 0;
X  long i ;
X
X  for ( i = 0 ; i < len ; i++ )
X    sum += *str++;
X
X  return sum;
X}
X
SHAR_EOF
chmod 0644 tran.c || echo "restore of tran.c fails"
set `wc -c tran.c`;Sum=$1
if test "$Sum" != "1670"
then echo original size 1670, current size $Sum;fi
fi
exit 0
--
-- <<Disclaimer: All opinions expressed are my own, of course.>>
-- Carl Ellison                        [e-mail]
-- Stratus Computer Inc.    M3-2-BKW        TEL: [phone]
-- 55 Fairbanks Boulevard ; Marlborough MA 01752-1298    FAX: [phone]