/* libpnm5.c - pnm utility library part 5
**
** Permutation generator, used by pnmstega and pnmdestega.
**
** Copyright (C) 1994 by Jef Poskanzer.
**
** Permission to use, copy, modify, and distribute this software and its
** documentation for any purpose and without fee is hereby granted, provided
** that the above copyright notice appear in all copies and that both that
** copyright notice and this permission notice appear in supporting
** documentation.  This software is provided "as is" without express or
** implied warranty.
*/

#include "pnm.h"

/* Generate a random permutation of plen elements from [0..psize).
**
** DO NOT MODIFY, IMPROVE, EXPAND, ENHANCE, OR IN ANY WAY CHANGE this
** generator.  It is used for cryptographic storage of data - if the
** sequence is changed, the data will become unrecoverable.
*/

#define TRIES1 30
#define TRIES2 30

static int get_bit( unsigned long n );

static unsigned long plen, psize, longs, low, high;
static unsigned long* bits;

/* Initialize the permutation. */
void
pm_init_perm( unsigned long pl, unsigned long ps )
    {
    unsigned long i;

    plen = pl;
    psize = ps;

    /* We want to be sure that an (L1, S1) permutation is identical to
    ** the L1-length initial subsequence of an (S1, S1) sequence.
    ** One way to accomplish this is to ignore the supplied length
    ** value, and always generate a full-length permutation.  For this
    ** implementation that's not particularly expensive, so why not.
    */
    plen = psize;

    /* Allocate a bit array to remember which elements are still available. */
    longs = ( plen + 31 ) / 32;
    bits = (unsigned long*) malloc( longs * sizeof(unsigned long) );
    if ( bits == (unsigned long*) 0 )
	pm_error( "out of memory" );
    for ( i = 0; i < longs; ++i )
	bits[i] = 0xffffffff;
    
    /* Set the high and low water marks. */
    low = 0;
    high = longs - 1;

    if ( longs * 32 != plen )
	/* The last longword is not full. */
	bits[high] = 0xffffffff >> ( longs * 32 - plen );
    }

/* Return the next element of the permutation. */
unsigned long
pm_next_perm( void )
    {
    unsigned long d, n;
    int i, v;

    /* First try looking randomly for an element to use. */
    d = high - low + 1;
    for ( i = 0; i < TRIES1; ++i )
	{
	n = pm_random() % d + low;
	v = get_bit( n );
	if ( v >= 0 )
	    return n * 32 + v;
	}

    /* Didn't find an element.  Do a more methodical search. */
    if ( pm_random() % 2 )
	{
	/* Search up from low water mark. */
	for ( ; low <= high; ++low )
	    {
	    v = get_bit( low );
	    if ( v >= 0 )
		return low * 32 + v;
	    }
	}
    else
	{
	/* Search down from high water mark. */
	for ( ; high >= low; --high )
	    {
	    v = get_bit( high );
	    if ( v >= 0 )
		return high * 32 + v;
	    }
	}

    /* No elements left! */
    pm_error( "ran off the end of the permutation" );
    }

static int
get_bit( unsigned long n )
    {
    unsigned long b;
    int i, j;
    static unsigned long bitmasks[32] = {
	0x00000001, 0x00000002, 0x00000004, 0x00000008,
	0x00000010, 0x00000020, 0x00000040, 0x00000080,
	0x00000100, 0x00000200, 0x00000400, 0x00000800,
	0x00001000, 0x00002000, 0x00004000, 0x00008000,
	0x00010000, 0x00020000, 0x00040000, 0x00080000,
	0x00100000, 0x00200000, 0x00400000, 0x00800000,
	0x01000000, 0x02000000, 0x04000000, 0x08000000,
	0x10000000, 0x20000000, 0x40000000, 0x80000000 };

    b = bits[n];

    /* Check whether there are any bits to be found in this longword. */
    if ( b == 0 )
	return -1;

    /* First search randomly. */
    for ( i = 0; i < TRIES2; ++i )
	{
	j = pm_random() % 32;
	if ( b & bitmasks[j] )
	    {
	    bits[n] &= ~bitmasks[j];
	    return j;
	    }
	}

    /* Didn't find any.  Search more methodically. */
    if ( pm_random() % 2 )
	{
	for ( j = 0; j < 32; ++j )
	    if ( b & bitmasks[j] )
		{
		bits[n] &= ~bitmasks[j];
		return j;
		}
	}
    else
	{
	for ( j = 31; j >= 0; --j )
	    if ( b & bitmasks[j] )
		{
		bits[n] &= ~bitmasks[j];
		return j;
		}
	}

    pm_error( "couldn't find bit - shouldn't happen" );
    }

/* Another routine used by both pnmstega and pnmdestega. */
void
pm_map_comps( int comp_r, int comp_g, int comp_b, int num_comps, int comp_map[] )
    {
    comp_map[0] = comp_map[1] = comp_map[2] = 12345;
    switch ( num_comps )
	{
	case 1:
	if ( comp_r )
	    comp_map[0] = 0;
	else if ( comp_g )
	    comp_map[0] = 1;
	else
	    comp_map[0] = 2;
	break;
	case 2:
	if ( comp_r )
	    {
	    comp_map[0] = 0;
	    if ( comp_g )
		comp_map[1] = 1;
	    else
		comp_map[1] = 2;
	    }
	else
	    {
	    comp_map[0] = 1;
	    comp_map[1] = 2;
	    }
	break;
	case 3:
	comp_map[0] = 0;
	comp_map[1] = 1;
	comp_map[2] = 2;
	break;
	default:
	pm_error( "shouldn't happen" );
	}
    }