Subversion Repositories bluespec_md6

/* File:    md6_mode.c

** Author:  Ronald L. Rivest

** Address: Room 32G-692 Stata Center

**          32 Vassar Street

**          Cambridge, MA 02139

** Email:   rivest@mit.edu

** Date:    9/25/2008

**

** (The following license is known as "The MIT License")

**

** Copyright (c) 2008 Ronald L. Rivest

**

** Permission is hereby granted, free of charge, to any person obtaining a copy

** of this software and associated documentation files (the "Software"), to deal

** in the Software without restriction, including without limitation the rights

** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

** copies of the Software, and to permit persons to whom the Software is

** furnished to do so, subject to the following conditions:

**

** The above copyright notice and this permission notice shall be included in

** all copies or substantial portions of the Software.

**

** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

** LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

** OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN

** THE SOFTWARE.

**

** (end of license)

**

** This is part of the definition of the MD6 hash function.

** The files defining the md6 hash function are:

**    md6.h

**    md6_compress.c

**    md6_mode.c

**

** The files defining the interface between MD6 and the NIST SHA-3

** API are:

**    md6_nist.h

**    md6_nist.c

** The NIST SHA-3 API is defined in:

**    http://www.csrc.nist.gov/groups/ST/hash/documents/SHA3-C-API.pdf

**

** See  http://groups.csail.mit.edu/cis/md6  for more information.

*/

/* MD6 standard mode of operation

**

** Defines the following interfaces (documentation copied from md6.h)

*/

#if 0

/* The next routines are used according to the pattern:

**    md6_init        (or md6_full_init if you use additional parameters)

**    md6_update         (once for each portion of the data to be hashed)

**    md6_final                           (to finish up hash computation)

** Note: md6_final can return the hash value to a desired location, but

** hash value also remains available inside the md6_state, in both binary

** and hex formats (state->hashval and state->hexhashval).

*/

extern int md6_init( md6_state *st,             /* state to initialize */

                     int d                          /* hash bit length */

                     );

extern int md6_full_init( md6_state *st,        /* state to initialize */

                          int d,                    /* hash bit length */

                          unsigned char *key,       /* OK to give NULL */

                          int keylen,       /* (in bytes) OK to give 0 */

                          int L,     /* mode; OK to give md6_default_L */

                          int r                    /* number of rounds */

                          );

extern int md6_update( md6_state *st,             /* initialized state */

                       unsigned char *data,            /* data portion */

                       uint64_t datalen          /* its length in bits */

                       );

extern int md6_final( md6_state *st,            /* initialized/updated */

                      unsigned char *hashval,      /* output; NULL OK  */

                      );

/* The next routines compute a hash for a message given all at once.

** The resulting hash value is returned to a specified location.

** Only one call is needed.  Use md6_hash for the standard md6 hash,

** and md6_full_hash if you want to specify additional parameters.

*/

extern int md6_hash( int d,                         /* hash bit length */

                     unsigned char *data,     /* complete data to hash */

                     uint64_t datalen            /* its length in bits */

                     unsigned char *hashval,                 /* output */

                     );

extern int md6_full_hash( int d,                    /* hash bit length */

                          unsigned char *data,/* complete data to hash */

                          uint64_t datalen,      /* its length in bits */

                          unsigned char *key,       /* OK to give NULL */

                          int keylen,       /* (in bytes) OK to give 0 */

                          int L,     /* mode; OK to give md6_default_L */

                          int r,                   /* number of rounds */

                          unsigned char *hashval,            /* output */

                          );

#endif

#include <assert.h>

#include <stdio.h> 

#include <string.h>

#include "md6.h"

/* MD6 constants independent of mode of operation (from md6.h) */

#define w md6_w     /* # bits in a word                   (64) */

#define n md6_n     /* # words in compression input       (89) */

#define c md6_c     /* # words in compression output      (16) */

/* MD6 constants needed for mode of operation                  */

#define q md6_q     /* # words in Q                       (15) */

#define k md6_k     /* # words in key (aka salt)          (8)  */

#define u md6_u     /* # words in unique node ID          (1)  */

#define v md6_v     /* # words in control word            (1)  */

#define b md6_b     /* # data words per compression block (64) */

/* Useful macros: min and max */

#ifndef min

#define min(a,b) ((a)<(b)? (a) : (b))

#endif

#ifndef max

#define max(a,b) ((a)>(b)? (a) : (b))

#endif

/* Default number of rounds (as a function of digest size d)   */

int md6_default_r( int d )

{

  /* Default number of rounds is forty plus floor(d/4) */

  return 40 + (d/4);

}

/* MD6 Constant Vector Q

** Q = initial 960 bits of fractional part of sqrt(6)

**

** Given here for w = 64, 32, 16, and 8, although only

** w = 64 is needed for the standard version of MD6.

*/

#if (w==64)                      /* for standard version */

/* 15 64-bit words */

static const md6_word Q[15] =

  {

    0x7311c2812425cfa0ULL,

    0x6432286434aac8e7ULL,

    0xb60450e9ef68b7c1ULL,

    0xe8fb23908d9f06f1ULL,

    0xdd2e76cba691e5bfULL,

    0x0cd0d63b2c30bc41ULL,

    0x1f8ccf6823058f8aULL,

    0x54e5ed5b88e3775dULL,

    0x4ad12aae0a6d6031ULL,

    0x3e7f16bb88222e0dULL,

    0x8af8671d3fb50c2cULL,

    0x995ad1178bd25c31ULL,

    0xc878c1dd04c4b633ULL,

    0x3b72066c7a1552acULL,

    0x0d6f3522631effcbULL,

  };

#endif

#if (w==32)                      /* for variant version */

/* 30 32-bit words */

static const md6_word Q[30] =

  {

    0x7311c281UL, 0x2425cfa0UL,

    0x64322864UL, 0x34aac8e7UL,

    0xb60450e9UL, 0xef68b7c1UL,

    0xe8fb2390UL, 0x8d9f06f1UL,

    0xdd2e76cbUL, 0xa691e5bfUL,

    0x0cd0d63bUL, 0x2c30bc41UL,

    0x1f8ccf68UL, 0x23058f8aUL,

    0x54e5ed5bUL, 0x88e3775dUL,

    0x4ad12aaeUL, 0x0a6d6031UL,

    0x3e7f16bbUL, 0x88222e0dUL,

    0x8af8671dUL, 0x3fb50c2cUL,

    0x995ad117UL, 0x8bd25c31UL,

    0xc878c1ddUL, 0x04c4b633UL,

    0x3b72066cUL, 0x7a1552acUL,

    0x0d6f3522UL, 0x631effcbUL,

  };

#endif

/* MD6 Constant Vector Q (continued).

*/

#if (w==16)                      /* for variant version */

/* 60 16-bit words */

static const md6_word Q[60] =

  {

    0x7311, 0xc281, 0x2425, 0xcfa0,

    0x6432, 0x2864, 0x34aa, 0xc8e7,

    0xb604, 0x50e9, 0xef68, 0xb7c1,

    0xe8fb, 0x2390, 0x8d9f, 0x06f1,

    0xdd2e, 0x76cb, 0xa691, 0xe5bf,

    0x0cd0, 0xd63b, 0x2c30, 0xbc41,

    0x1f8c, 0xcf68, 0x2305, 0x8f8a,

    0x54e5, 0xed5b, 0x88e3, 0x775d,

    0x4ad1, 0x2aae, 0x0a6d, 0x6031,

    0x3e7f, 0x16bb, 0x8822, 0x2e0d,

    0x8af8, 0x671d, 0x3fb5, 0x0c2c,

    0x995a, 0xd117, 0x8bd2, 0x5c31,

    0xc878, 0xc1dd, 0x04c4, 0xb633,

    0x3b72, 0x066c, 0x7a15, 0x52ac,

    0x0d6f, 0x3522, 0x631e, 0xffcb,

  };

#endif

#if (w==8)                      /* for variant version */

/* 120 8-bit words */

static const md6_word Q[120] =

  {

    0x73, 0x11, 0xc2, 0x81, 0x24, 0x25, 0xcf, 0xa0,

    0x64, 0x32, 0x28, 0x64, 0x34, 0xaa, 0xc8, 0xe7,

    0xb6, 0x04, 0x50, 0xe9, 0xef, 0x68, 0xb7, 0xc1,

    0xe8, 0xfb, 0x23, 0x90, 0x8d, 0x9f, 0x06, 0xf1,

    0xdd, 0x2e, 0x76, 0xcb, 0xa6, 0x91, 0xe5, 0xbf,

    0x0c, 0xd0, 0xd6, 0x3b, 0x2c, 0x30, 0xbc, 0x41,

    0x1f, 0x8c, 0xcf, 0x68, 0x23, 0x05, 0x8f, 0x8a,

    0x54, 0xe5, 0xed, 0x5b, 0x88, 0xe3, 0x77, 0x5d,

    0x4a, 0xd1, 0x2a, 0xae, 0x0a, 0x6d, 0x60, 0x31,

    0x3e, 0x7f, 0x16, 0xbb, 0x88, 0x22, 0x2e, 0x0d,

    0x8a, 0xf8, 0x67, 0x1d, 0x3f, 0xb5, 0x0c, 0x2c,

    0x99, 0x5a, 0xd1, 0x17, 0x8b, 0xd2, 0x5c, 0x31,

    0xc8, 0x78, 0xc1, 0xdd, 0x04, 0xc4, 0xb6, 0x33,

    0x3b, 0x72, 0x06, 0x6c, 0x7a, 0x15, 0x52, 0xac,

    0x0d, 0x6f, 0x35, 0x22, 0x63, 0x1e, 0xff, 0xcb,

  };

#endif

/* Endianness.

*/

/* routines for dealing with byte ordering */

int md6_byte_order = 0;

/* md6_byte_order describes the endianness of the

** underlying machine:

** 0 = unknown

** 1 = little-endian

** 2 = big-endian

*/

/* Macros to detect machine byte order; these

** presume that md6_byte_order has been setup by

** md6_detect_byte_order()

*/

#define MD6_LITTLE_ENDIAN (md6_byte_order == 1)

#define MD6_BIG_ENDIAN    (md6_byte_order == 2)

void md6_detect_byte_order( void )

/* determine if underlying machine is little-endian or big-endian

** set global variable md6_byte_order to reflect result

** Written to work for any w.

*/

{ md6_word x = 1 | (((md6_word)2)<<(w-8));

  unsigned char *cp = (unsigned char *)&x;

  if ( *cp == 1 )        md6_byte_order = 1;      /* little-endian */

  else if ( *cp == 2 )   md6_byte_order = 2;      /* big-endian    */

  else                   md6_byte_order = 0;      /* unknown       */

}

md6_word md6_byte_reverse( md6_word x )

/* return byte-reversal of md6_word x.

** Written to work for any w, w=8,16,32,64.

*/

{

#define mask8  ((md6_word)0x00ff00ff00ff00ffULL)

#define mask16 ((md6_word)0x0000ffff0000ffffULL)

#if (w==64)

  x = (x << 32) | (x >> 32);

#endif

#if (w >= 32)

  x = ((x & mask16) << 16) | ((x & ~mask16) >> 16);

#endif

#if (w >= 16)

  x = ((x & mask8) << 8) | ((x & ~mask8) >> 8);

#endif

  return x;

}

void md6_reverse_little_endian( md6_word *x, int count )

/* Byte-reverse words x[0...count-1] if machine is little_endian */

{

  int i;

  if (MD6_LITTLE_ENDIAN)

    for (i=0;i<count;i++)

      x[i] = md6_byte_reverse(x[i]);

}

/* Appending one bit string onto another.

*/

void append_bits( unsigned char *dest, unsigned int destlen,

                  unsigned char *src,  unsigned int srclen )

/* Append bit string src to the end of bit string dest

** Input:

**     dest         a bit string of destlen bits, starting in dest[0]

**                  if destlen is not a multiple of 8, the high-order

**                  bits are used first

**     src          a bit string of srclen bits, starting in src[0]

**                  if srclen is not a multiple of 8, the high-order

**                  bits are used first

** Modifies:

**     dest         when append_bits returns, dest will be modified to

**                  be a bit-string of length (destlen+srclen).

**                  zeros will fill any unused bit positions in the

**                  last byte.

*/

{ int i, di, accumlen;

  uint16_t accum;

  int srcbytes;

  if (srclen == 0) return;

  /* Initialize accum, accumlen, and di */

  accum = 0;    /* accumulates bits waiting to be moved, right-justified */

  accumlen = 0; /* number of bits in accumulator */

  if (destlen%8 != 0)

    { accumlen = destlen%8;

      accum = dest[destlen/8];        /* grab partial byte from dest     */

      accum = accum >> (8-accumlen);  /* right-justify it in accumulator */

    }

  di = destlen/8;        /* index of where next byte will go within dest */

  /* Now process each byte of src */

  srcbytes = (srclen+7)/8;   /* number of bytes (full or partial) in src */

  for (i=0;i<srcbytes;i++)

    { /* shift good bits from src[i] into accum */

      if (i != srcbytes-1) /* not last byte */

        { accum = (accum << 8) ^ src[i];

          accumlen += 8;

        }

      else /* last byte */

        { int newbits = ((srclen%8 == 0) ? 8 : (srclen%8));

          accum = (accum << newbits) | (src[i] >> (8-newbits));

          accumlen += newbits;

        }

      /* do as many high-order bits of accum as you can (or need to) */

      while ( ( (i != srcbytes-1) & (accumlen >= 8) ) ||

              ( (i == srcbytes-1) & (accumlen > 0) ) )

        { int numbits = min(8,accumlen);

          unsigned char bits;

          bits = accum >> (accumlen - numbits);    /* right justified */

          bits = bits << (8-numbits);              /* left justified  */

          bits &= (0xff00 >> numbits);             /* mask            */

          dest[di++] = bits;                       /* save            */

          accumlen -= numbits;

        }

    }

}

/* State initialization. (md6_full_init, with all parameters specified)

**

*/

int md6_full_init( md6_state *st,       /* uninitialized state to use */

                   int d,                          /* hash bit length */

                   unsigned char *key,        /* key; OK to give NULL */

                   int keylen,     /* keylength (bytes); OK to give 0 */

                   int L,           /* mode; OK to give md6_default_L */

                   int r                          /* number of rounds */

                   )

/* Initialize md6_state

** Input:

**     st         md6_state to be initialized

**     d          desired hash bit length 1 <= d <= w*(c/2)    (<=512 bits)

**     key        key (aka salt) for this hash computation     (byte array)

**                defaults to all-zero key if key==NULL or keylen==0

**     keylen     length of key in bytes; 0 <= keylen <= (k*8) (<=64 bytes)

**     L          md6 mode parameter; 0 <= L <= 255

**                md6.h defines md6_default_L for when you want default

**     r          number of rounds; 0 <= r <= 255

** Output:

**     updates components of state

**     returns one of the following:

**       MD6_SUCCESS

**       MD6_NULLSTATE

**       MD6_BADKEYLEN

**       MD6_BADHASHLEN

*/

{ /* check that md6_full_init input parameters make some sense */

  if (st == NULL) return MD6_NULLSTATE;

  if ( (key != NULL) && ((keylen < 0) || (keylen > k*(w/8))) )

    return MD6_BADKEYLEN;

  if ( d < 1 || d > 512 || d > w*c/2 ) return MD6_BADHASHLEN;

  md6_detect_byte_order();

  memset(st,0,sizeof(md6_state));  /* clear state to zero */

  st->d = d;                       /* save hashbitlen */

  if (key != NULL && keylen > 0)   /* if no key given, use memset zeros*/

    { memcpy(st->K,key,keylen);    /* else save key (with zeros added) */

      st->keylen = keylen;

      /* handle endian-ness */       /* first byte went into high end */

      md6_reverse_little_endian(st->K,k);

    }

  else

    st->keylen = 0;

  if ( (L<0) | (L>255) ) return MD6_BAD_L;

  st->L = L;

  if ( (r<0) | (r>255) ) return MD6_BAD_r;

  st->r = r;

  st->initialized = 1;

  st->top = 1;

  /* if SEQ mode for level 1; use IV=0  */

  /* zero bits already there by memset; */

  /* we just need to set st->bits[1]    */

  if (L==0) st->bits[1] = c*w;

  compression_hook = NULL;     /* just to be sure default is "not set" */

  return MD6_SUCCESS;

}

/* State initialization. (md6_init, which defaults most parameters.)

**

*/

int md6_init( md6_state *st,

              int d

              )

/* Same as md6_full_init, but with default key, L, and r */

{ return md6_full_init(st,

                       d,

                       NULL,

                       0,

                       md6_default_L,

                       md6_default_r(d)

                       );

}

/* Data structure notes.

*/

/*

Here are some notes on the data structures used (inside state).

* The variable B[] is a stack of length-b (b-64) word records,

  each corresponding to a node in the tree.  B[ell] corresponds

  to a node at level ell.  Specifically, it represents the record which,

  when compressed, will yield the value at that level. (It only

  contains the data payload, not the auxiliary information.)

  Note that B[i] is used to store the *inputs* to the computation at

  level i, not the output for the node at that level.

  Thus, for example, the message input is stored in B[1], not B[0].

* Level 0 is not used.  The message bytes are placed into B[1].

* top is the largest ell for which B[ell] has received data,

  or is equal to 1 in case no data has been received yet at all.

* top is never greater than L+1.  If B[L+1] is

  compressed, the result is put back into B[L+1]  (this is SEQ).

* bits[ell] says how many bits have been placed into

  B[ell].  An invariant maintained is that of the bits in B[ell],

  only the first bits[ell] may be nonzero; the following bits must be zero.

* The B nodes may have somewhat different formats, depending on the level:

  -- Level 1 node contains a variable-length bit-string, and so

  -- Levels 2...top always receive data in c-word chunks (from

     children), so for them bits[ell] is between 0 and b*w,

     inclusive, but is also a multiple of cw.  We can think of these

     nodes as have (b/c) (i.e. 4) "slots" for chunks.

  -- Level L+1 is special, in that the first c words of B are dedicated

     to the "chaining variable" (or IV, for the first node on the level).

* When the hashing is over, B[top] will contain the

  final hash value, in the first or second (if top = L+1) slot.

*/

/* Compress one block -- compress data at a node (md6_compress_block).

*/

int md6_compress_block( md6_word *C,

                        md6_state *st,

                        int ell,

                        int z

                        )

/* compress block at level ell, and put c-word result into C.

** Input:

**     st         current md6 computation state

**     ell        0 <= ell < max_stack_height-1

**     z          z = 1 if this is very last compression; else 0

** Output:

**     C          c-word array to put result in

** Modifies:

**     st->bits[ell]  (zeroed)

**     st->i_for_level[ell] (incremented)

**     st->B[ell] (zeroed)

**     st->compression_calls (incremented)

** Returns one of the following:

**     MD6_SUCCESS

**     MD6_NULLSTATE

**     MD6_STATENOTINIT

**     MD6_STACKUNDERFLOW

**     MD6_STACKOVERFLOW

*/

{ int p, err;

  /* check that input values are sensible */

  if ( st == NULL) return MD6_NULLSTATE;

  if ( st->initialized == 0 ) return MD6_STATENOTINIT;

  if ( ell < 0 ) return MD6_STACKUNDERFLOW;

  if ( ell >= md6_max_stack_height-1 ) return MD6_STACKOVERFLOW;

  st->compression_calls++;

  if (ell==1) /* leaf; hashing data; reverse bytes if nec. */

    { if (ell<(st->L + 1)) /* PAR (tree) node */

        md6_reverse_little_endian(&(st->B[ell][0]),b);

      else /* SEQ (sequential) node; don't reverse chaining vars */

        md6_reverse_little_endian(&(st->B[ell][c]),b-c);

    }

  p = b*w - st->bits[ell];          /* number of pad bits */

  err =

    md6_standard_compress(

      C,                                      /* C    */

      Q,                                      /* Q    */

      st->K,                                  /* K    */

      ell, st->i_for_level[ell],              /* -> U */

      st->r, st->L, z, p, st->keylen, st->d,  /* -> V */

      st->B[ell]                              /* B    */

                           );

  if (err) return err;

  st->bits[ell] = 0; /* clear bits used count this level */

  st->i_for_level[ell]++;

  memset(&(st->B[ell][0]),0,b*sizeof(md6_word));     /* clear B[ell] */

  return MD6_SUCCESS;

}

/* Process (compress) a node and its compressible ancestors.

*/

int md6_process( md6_state *st,

                 int ell,

                 int final )

/*

** Do processing of level ell (and higher, if necessary) blocks.

**

** Input:

**     st         md6 state that has been accumulating message bits

**                and/or intermediate results

**     ell        level number of block to process

**     final      true if this routine called from md6_final

**                     (no more input will come)

**                false if more input will be coming

**                (This is not same notion as "final bit" (i.e. z)

**                 indicating the last compression operation.)

** Output (by side effect on state):

**     Sets st->hashval to final chaining value on final compression.

** Returns one of the following:

**     MD6_SUCCESS

**     MD6_NULLSTATE

**     MD6_STATENOTINIT

*/

{ int err, z, next_level;

  md6_word C[c];

  /* check that input values are sensible */

  if ( st == NULL) return MD6_NULLSTATE;

  if ( st->initialized == 0 ) return MD6_STATENOTINIT;

  if (!final) /* not final -- more input will be coming */

    { /* if not final and block on this level not full, nothing to do */

      if ( st->bits[ell] < b*w )

        return MD6_SUCCESS;

      /* else fall through to compress this full block,

      **       since more input will be coming

      */

    }

  else /* final -- no more input will be coming */

    { if ( ell == st->top )

        { if (ell == (st->L + 1)) /* SEQ node */

            { if ( st->bits[ell]==c*w && st->i_for_level[ell]>0 )

                return MD6_SUCCESS;

              /* else (bits>cw or i==0, so fall thru to compress */

            }

           else /* st->top == ell <= st->L so we are at top tree node */

             { if ( ell>1 && st->bits[ell]==c*w)

                 return MD6_SUCCESS;

               /* else (ell==1 or bits>cw, so fall thru to compress */

             }

        }

      /* else (here ell < st->top so fall through to compress */

    }

  /* compress block at this level; result goes into C */

  /* first set z to 1 iff this is the very last compression */

  z = 0; if (final && (ell == st->top)) z = 1;

  if ((err = md6_compress_block(C,st,ell,z)))

      return err;

  if (z==1) /* save final chaining value in st->hashval */

    { memcpy( st->hashval, C, md6_c*(w/8) );

      return MD6_SUCCESS;

    }

  /* where should result go? To "next level" */

  next_level = min(ell+1,st->L+1);

  /* Start sequential mode with IV=0 at that level if necessary

  ** (All that is needed is to set bits[next_level] to c*w,

  ** since the bits themselves are already zeroed, either

  ** initially, or at the end of md6_compress_block.)

  */

  if (next_level == st->L + 1

      && st->i_for_level[next_level]==0

      && st->bits[next_level]==0 )

    st->bits[next_level] = c*w;

  /* now copy C onto next level */

  memcpy((char *)st->B[next_level] + st->bits[next_level]/8,

         C,

         c*(w/8));

  st->bits[next_level] += c*w;

  if (next_level > st->top) st->top = next_level;

  return md6_process(st,next_level,final);

}

/* Update -- incorporate data string into hash computation.

*/

int md6_update( md6_state *st,

                unsigned char *data,

                uint64_t databitlen )

/* Process input byte string data, updating state to reflect result

** Input:

**     st               already initialized state to be updated

**     data             byte string of length databitlen bits

**                      to be processed (aka "M")

**     databitlen       number of bits in string data (aka "m")

** Modifies:

**     st               updated to reflect input of data

*/

{ unsigned int j, portion_size;

  int err;

  /* check that input values are sensible */

  if ( st == NULL ) return MD6_NULLSTATE;

  if ( st->initialized == 0 ) return MD6_STATENOTINIT;

  if ( data == NULL ) return MD6_NULLDATA;

  j = 0; /* j = number of bits processed so far with this update */

  while (j<databitlen)

    { /* handle input string in portions (portion_size in bits)

      ** portion_size may be zero (level 1 data block might be full,

      ** having size b*w bits) */

      portion_size = min(databitlen-j,

                         (unsigned int)(b*w-(st->bits[1])));

      if ((portion_size % 8 == 0) &&

          (st->bits[1] % 8 == 0) &&

          (j % 8 == 0))

        { /* use mempy to handle easy, but most common, case */

          memcpy((char *)st->B[1] + st->bits[1]/8,

                 &(data[j/8]),

                 portion_size/8);

        }

      else /* handle messy case where shifting is needed */

        { append_bits((unsigned char *)st->B[1], /* dest */

                      st->bits[1],   /* dest current bit size */

                      &(data[j/8]),  /* src */

                      portion_size); /* src size in bits  */

        }

      j += portion_size;

      st->bits[1] += portion_size;

      st->bits_processed += portion_size;

      /* compress level-1 block if it is now full

         but we're not done yet */

      if (st->bits[1] == b*w && j<databitlen)