/*
 * Copyright (C) DSTC Pty Ltd (ACN 052 372 577) 1997.
 *
 * Any party obtaining a copy of this file from DSTC Pty Ltd, directly
 * or indirectly, is granted, free of charge, a full and unrestricted
 * irrevocable, world-wide, paid up, royalty-free, nonexclusive right and
 * license to deal in this software (the "Software"), including without
 * limitation the rights to use, copy, modify, merge, publish, distribute,
 * sublicense, and/or sell copies of the Software, and to permit persons
 * who receive copies from any such party to do so, with the only
 * requirement being that all copyright notices remain intact.
 *
 * This software is being provided "AS IS" without warranty of any kind,
 * express, implied or otherwise, including without limitation, any
 * warranty of merchantability or fitness for a particular purpose.
 *
 * In no event shall DSTC Pty Ltd be liable for any special, incidental,
 * indirect or consequential damages of any kind, or any damages whatsoever
 * resulting from loss of use, data or profits, whether or not advised of
 * the possibility of damage, and on any theory of liability, arising out
 * of or in connection with the use or performance of this software.
 *
 * DSTC Pty Ltd welcomes comments and bug fixes related to this software.
 * Please address any queries, comments or bug fixes (please include
 * the name and version of the software you are using and details
 * of your operating system version) to the address below:
 *
 *       DSTC Pty Ltd
 *       Level 7, Gehrmann Labs
 *       University of Queensland
 *       St Lucia, 4072
 *       Tel: +61 7 365 4310
 *       Fax: +61 7 365 4311
 *       Email: Enquiries@dstc.edu.au
 */

/*---------------------------------------------------------------------------*/

/*
 * Revision history:
 *
 * 15 Aug 97: Changed init_codevals() to use a loop for initialization
 *            instead of in-line code. Thanks to Rich Salz for suggesting
 *	      this.
 *
 * 20 Oct 97: Changed prefix to add a colon separator. Thanks to Steve
 *	      Vinoski for pointing out that this was necessary for
 *	      use of IORs in web browsers.
 *
 *	      Added example for little-endian nil IOR. Thanks to Martin
 *	      Chilvers for pointing out that there are two representations
 *	      of nil IORs.
 */

/*---------------------------------------------------------------------------*/

/*
 * cdr_to_ior2(),
 * ior2_to_cdr()	- convert from CDR to IOR2 format and vice versa
 *
 * cdr_size()		- return the CDR size of an IOR (both old and new)
 *
 * IOR2 encoded strings are typically 40% - 45% shorter than the old IOR
 * format, depending on the specific IOR (compression improves for
 * longer IORs).
 *
 * Big-endian nil IORs are compressed by 61%, from
 * "IOR:00000000000000010000000000000000" to "IOR2:000g=74=8".
 *
 * Little-endian nil IORs are compressed by 56%, from
 * "IOR:01000000010000000000000000000000" to "IOR2:000g0g=14=c".
 *
 * An IOR in IOR2 format is a well-behaved string - it contains only digits,
 * lower and upper case letters, and the letters ':', '-', '+' and '='.
 * This means it can easily be used on the command line, as a database
 * field value, or for line-oriented file I/O (the stringified IOR does
 * not contain embedded control characters, white space, or newline characters).
 * IOR2 references can also be represented as an ASN.1 printable string.
 *
 * It is possible to compress IORs further, by using a Lempel-Ziv or
 * similar encoding, but this sacrifices the printable nature of the string
 * (binary values need to be used to get the last few percent of compression).
 * The algorithm used here is a compromise - it leaves around 20% redundancy
 * in the compressed IOR, but keeps the resultant string printable.
 *
 * The code below makes no assumptions about codesets, so it works for both
 * ASCII and EBCDIC. There are also no assumptions about character
 * ordering (or groups of characters occupying adjacent code positions),
 * so this source can be used with any single-byte code set.
 * To remain portable, the code table is initialized at run-time.
 *
 * The code compiles cleanly with both ANSI-C and C++ compilers.
 * It works with both signed and unsigned char implementations and
 * makes no assumptions about byte ordering. 2's complement representation
 * is *not* assumed. The code will work on 16 bit machines and is suitable
 * for use in free-standing implementations (it does not require libc or
 * other libraries).
 *
 * The code is thread-safe and reentrant, except for the run-time
 * initialization of the decode array. To get thread safety for that,
 * the 'once' guard variable and the call to the initialization function
 * (init_codevals) need to be protected by a mutex.
 *
 * Performance of the conversions between CDR and IOR2 (and back) should not
 * be a concern. The code below sacrifices a lot of efficiency to remain
 * portable. Even so, on an HP715/100 workstation, the code achieves:
 *
 * CDR length | Direction   | Conversions/sec
 * ------------------------------------------
 *    308     | cdr_to_ior2 |     6500
 *    308     | ior2_to_cdr |     8500
 *    212     | cdr_to_ior2 |     9500
 *    212     | ior2_to_cdr |	 12500
 *
 * So even for a rather long IOR with 308 bytes of CDR, conversion speed
 * won't be an issue.
 *
 * Not surprisingly, the cost of conversion increases linearly with the
 * size of the reference.
 *
 * The algorithm chosen for this implementation minimizes code size
 * (the PA-RISC object code size is 2.5 kB for code and data).
 */

/*---------------------------------------------------------------------------*/

#include	"ior2.h"

/*---------------------------------------------------------------------------*/

/*
 * decode is an array of code values. It maps a character (the index)
 * to a value. The array is initialized at run-time to make sure
 * the code works with both ASCII and EBCDIC (or other codes).
 *
 * The mapping for the decode array is
 *
 *	'0' -> 0
 *	...
 *	'9' -> 9
 *	'a' -> 10
 *	...
 *	'z' -> 35
 *	'A' -> 36
 *	...
 *	'Z' -> 61
 *	'-' -> 62
 *	'+' -> 63
 *
 * The array is sparse and initialized only for the relevant
 * lookup positions (the unsigned byte value is used directly as an index).
 * Again, this gives codeset independence (and improves speed a little).
 */
static int decode[256];

/*
 * Guard to do lazy initialization of decode array.
 */
static int once = 0;

/*
 * Inverse mapping of decode array. Maps a value to a character.
 */
static const char code[] = "0123456789"
			   "abcdefghijklmnopqrstuvwxyz"
			   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
			   "-+";

/*
 * ZERO_CODE ('=') is a special marker for run-length encoding of
 * consecutive zeros. It must not occur in the codeval or code arrays.
 *
 * Runs of zeros are encoded as:
 *
 *	Number of zeros		Code
 *	----------------------------
 *		 3		=0
 *		 4		=1
 *		...		...
 *		12		=9
 *		13		=a
 *		14		=b
 *		...		...
 *		38		=z
 *		39		=A
 *		40		=B
 *		...		...
 *		64		=Z
 *		65		=-
 *		66		=+
 *
 * In other words, the number of zeros in a run is encoded by the byte
 * following the '=' character.
 *
 * For encoding, that byte value is
 *
 *	code[zeros - 3]
 *
 * For decoding, the run length is reconstructed by using the value
 * of the byte following the '=' marker as an index into the decode
 * array and adding 3:
 *
 *	decode[byte] + 3
 *		
 * Runs of more than 66 zeros are encoded by two consecutive run-length
 * encodings. For example:
 *
 *	(70 zeros) -> =+=1
 *	
 * After each run, at least three zeros must be left for another run,
 * otherwise the normal encoding is used. For example:
 *
 *	(68 zeros) -> =+00
 */
static const char ZERO_CODE = '=';

/*
 * Some powers of two. The code uses div (/) and mod (%) operations to
 * set and clear bits (to avoid assuming 2's complement representation).
 * Making constants here keeps the code readable. We use the preprocessor
 * (instead of real constants) because real constants can slow the code
 * down by more than a factor of two with some compilers.
 */
#define	P2_18	262144		/* 2^18, 256 kB */
#define	P2_12	4096		/* 2^12, 4 kB */
#define	P2_6	64		/* 2^6,  64 bytes */
#define	P2_4	16		/* 2^4,  16 bytes */
#define	P2_2	4		/* 2^2,  4 bytes */

/*---------------------------------------------------------------------------*/

/*
 * Initialize the decode array with the numeric codes for each character.
 * We do this at run time to make it work for both ASCII and EBCDIC.
 */

static void
init_codevals()
{
	int i;

	for (i = 0; i < sizeof(code) - 1; i++)
		decode[(unsigned)code[i]] = i;
}

/*---------------------------------------------------------------------------*/

/*
 * Convert 'cdrsize' bytes in the 'cdr' buffer into IOR2 format in 'ior2'.
 * 'ior2size' must be set to the size of the 'ior2' buffer.
 *
 * Return value:
 *
 *	- A non-zero return value indicates the actual number of bytes
 *	  written into 'ior2' (the count includes the terminating NUL byte).
 *
 *	- A zero return value indicates that the length of the 'ior2'
 *	  buffer as specified by 'ior2size' was insufficient to hold
 *	  the encoded IOR.
 */

size_t
cdr_to_ior2(const void *cdr, size_t cdrsize, char *ior2, size_t ior2size)
{
	size_t			val;		/* Temporary */
	unsigned		pos;		/* State variable */
	unsigned		zeros;		/* Num zeros blocks in run */
	size_t			ior2len;	/* Length of ior2 */
	const unsigned char	*cdrp;		/* First byte of CDR */
	size_t			cdrlen;		/* Length of cdr */
	int			last_iter;	/* True for last byte of CDR */

	/*
	 * Need 9 bytes for prefix and length field.
	 */
	if (ior2size < 9)
		return 0;

	/*
	 * Set prefix.
	 */
	*ior2++ = 'I';
	*ior2++ = 'O';
	*ior2++ = 'R';
	*ior2++ = '2';
	*ior2++ = ':';

	/*
	 * Encode 4-byte CDR length.
	 */
	val = cdrsize;
	*ior2++ = code[val / P2_18];
	val %= P2_18;
	*ior2++ = code[val / P2_12];
	val %= P2_12;
	*ior2++ = code[val / P2_6];
	*ior2++ = code[val % P2_6];

	ior2len = 9;	/* Five bytes for prefix, plus four bytes for length */

	/*
	 * Repeatedly peel off the next six CDR bits.
	 */
	cdrp = (const unsigned char *)cdr;
	cdrlen = 0;
	zeros = 0;
	pos = 0;
	while (cdrlen < cdrsize) {

		/*
		 * Work out which bits to mask out in this iteration.
		 */
		last_iter = (cdrlen == cdrsize - 1 && pos != 0);
		switch (pos) {
		case 0:
			/*
			 * High-order 6 bits in current byte.
			 */
			val = cdrp[cdrlen] / P2_2;
			break;
		case 1:
			/*
			 * Low-order 2 bits in current byte
			 * and high-order 4 bits in next byte.
			 */
			val = cdrp[cdrlen] % P2_2 * P2_4;
			if (!last_iter)
				val += cdrp[cdrlen + 1] / P2_4;
			cdrlen++;
			break;
		case 2:
			/*
			 * Low-order 4 bits in current byte
			 * and high-order 2 bits in next byte.
			 */
			val = cdrp[cdrlen] % P2_4 * P2_2;
			if (!last_iter)
				val += cdrp[cdrlen + 1] / P2_6;
			cdrlen++;
			break;
		case 3:
			/*
			 * Low-order 6 bits in current byte.
			 */
			val = cdrp[cdrlen] % P2_6;
			cdrlen++;
			break;
		}
		pos = (pos + 1) % 4;

		if (val == 0) {
			/*
			 * val == 0 if a zero block was just peeled off.
			 * If so, increment count of zeros (or output
			 * a run if we have reached the limit of 66).
			 */
			if (zeros == 66) {
				if ((ior2len += 2) > ior2size)
					return 0;
				*ior2++ = ZERO_CODE;
				*ior2++ = code[zeros - 3];
				zeros = 1;
			} else {
				zeros++;
			}
		}
		if (val != 0 || last_iter) {
			/*
			 * We just peeled off a non-zero block, or we
			 * had a zero and this is the last iteration.
			 * Output any zeros found up to this point.
			 * If this is not the last iteration, output
			 * the code for the non-zero block.
			 */
			switch (zeros) {
			case 2:
				if (++ior2len > ior2size)
					return 0;
				*ior2++ = code[0];
				/* FALLTHROUGH */
			case 1:
				if (++ior2len > ior2size)
					return 0;
				*ior2++ = code[0];
				/* FALLTHROUGH */
			case 0:
				if (val != 0) {
					if (++ior2len > ior2size)
						return 0;
					*ior2++ = code[val];
				}
				break;
			default:
				if ((ior2len += 2) > ior2size)
					return 0;
				*ior2++ = ZERO_CODE;
				*ior2++ = code[zeros - 3];
				if (val != 0) {
					if (++ior2len > ior2size)
						return 0;
					*ior2++ = code[val];
				}
				break;
			}
			zeros = 0;
		}
	}

	/*
	 * Write terminating NUL.
	 */
	if (++ior2len > ior2size)
		return 0;
	*ior2 = '\0';

	return ior2len;
}

/*---------------------------------------------------------------------------*/

/*
 * Convert the reference in 'ior2' into CDR format. The 'cdr' buffer
 * receives the result. 'cdrsize' must be set to the length of the
 * 'cdr' buffer.
 *
 * Return value:
 *
 *	- A non-zero return value indicates the actual number of bytes
 *	  written into 'cdr'.
 *
 *	- A zero return value indicates failure:
 *
 *		- either the input IOR did not have an "IOR2" prefix, or
 *
 *		- the ior had a zero length field, or
 *
 *		- 'cdr' was too short to receive the decoded IOR.
 *
 * If the input IOR has a correct "IOR2:" prefix and non-zero length field,
 * it is otherwise assumed to be well-formed. Passing a malformed IOR with
 * an invalid length or illegal characters causes undefined behavior.
 */

size_t
ior2_to_cdr(const char *ior2, void *cdr, size_t cdrsize)
{
	unsigned char	*cdrp;		/* Next byte in CDR */
	unsigned	pos;		/* State variable */
	unsigned	zeros;		/* Num six-bit zeros blocks in run */
	unsigned	val;		/* Decoded value of current IOR2 byte */
	size_t		cdrlen;		/* Num CDR bytes written */
	unsigned	ior2_byte;	/* Current byte of ior2 */
	int		last_iter;	/* True for final 6-bit block */
	
	/*
	 * Initialize code value array (if not done yet).
	 */
	if (!once) {
		init_codevals();
		once = 1;
	}

	/*
	 * Test prefix.
	 */
	if (
	       *ior2++ != 'I'
	    || *ior2++ != 'O'
	    || *ior2++ != 'R'
	    || *ior2++ != '2'
	    || *ior2++ != ':') {
		return 0;
	}

	/*
	 * Test CDR length for sanity.
	 */
	if (cdrsize == 0)
		return 0;

	/*
	 * Decode 4-byte CDR length.
	 */
	cdrlen = decode[(unsigned)*ior2++] * P2_18;
	cdrlen += decode[(unsigned)*ior2++] * P2_12;
	cdrlen += decode[(unsigned)*ior2++] * P2_6;
	cdrlen += decode[(unsigned)*ior2++];
	if (cdrlen == 0)
		return 0;

	/*
	 * Make sure the output buffer is long enough to hold the result.
	 */
	if (cdrsize < cdrlen)
		return 0;

	/*
	 * Iterate over the IOR2 bytes, decoding each byte into
	 * six bits of CDR.
	 */
	cdrp = (unsigned char *)cdr;
	pos = 0;
	zeros = 0;
	while (zeros || (ior2_byte = *ior2) != '\0') {
		if (zeros) {
			/*
			 * val == 0 from previous iteration, do
			 * another zero.
			 */
			zeros--;
		} else if (ior2_byte == (unsigned)ZERO_CODE) {
			/*
			 * Deal with zero run.
			 */
			ior2++;				/* Skip '=' marker */
			ior2_byte = *ior2++;		/* Get run length */
			zeros = decode[ior2_byte] + 2;	/* Count of zeros */
			val = decode[0];		/* val = 0 */
		} else {
			/*
			 * Normal decoding.
			 */
			val = decode[ior2_byte];
			ior2++;
		}

		/*
		 * Use value of current byte, and copy
		 * bottom six bits of the value
		 * into CDR at the current output position.
		 */
		last_iter = (zeros == 0 && *ior2 == '\0');
		switch (pos) {
		case 0:
			*cdrp = val * P2_2;
			break;
		case 1:
			*cdrp++ += val / P2_4;
			if (!last_iter)
				*cdrp = val % P2_4 * P2_4;
			break;
		case 2:
			*cdrp++ += val / P2_2; 
			if (!last_iter)
				*cdrp = val % P2_2 * P2_6;
			break;
		case 3:
			*cdrp++ += val;
			break;
		}
		pos = (pos + 1) % 4;
	}

	return cdrlen;
}

/*---------------------------------------------------------------------------*/

/*
 * Return the number of CDR bytes required to hold a decoded IOR.
 */

size_t
cdr_size(const char *ior)
{
	size_t	len;

	/*
	 * Check prefix.
	 */
	if (*ior++ != 'I' || *ior++ != 'O' || *ior++ != 'R')
		return 0;
	
	/*
	 * Initialize code value array (if not done yet).
	 */
	if (!once) {
		init_codevals();
		once = 1;
	}

	/*
	 * Determine IOR version.
	 */
	if (*ior == '2' && *(ior + 1) == ':') {
		/*
		 * New IOR, decode length.
		 */
		ior += 2;
		len = decode[(unsigned)*ior++] * P2_18;
		len += decode[(unsigned)*ior++] * P2_12;
		len += decode[(unsigned)*ior++] * P2_6;
		len += decode[(unsigned)*ior];
	} else if (*ior == ':') {
		/*
		 * Old IOR, count number of digits. If a free-standing
		 * implementation is not required, calling strlen() here
		 * will probably be faster.
		 */
		++ior;
		len = 0;
		while (*ior++ != '\0')
			len++;
		len /= 2;
	} else {
		/*
		 * Not an "IOR:" or "IOR2:" prefix.
		 */
		len = 0;
	}

	return len;
}