xmill/XMill/BaseXNumCompressor.cpp

/*
This product contains certain software code or other information
("AT&T Software") proprietary to AT&T Corp. ("AT&T").  The AT&T
Software is provided to you "AS IS".  YOU ASSUME TOTAL RESPONSIBILITY
AND RISK FOR USE OF THE AT&T SOFTWARE.  AT&T DOES NOT MAKE, AND
EXPRESSLY DISCLAIMS, ANY EXPRESS OR IMPLIED WARRANTIES OF ANY KIND
WHATSOEVER, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE, WARRANTIES OF
TITLE OR NON-INFRINGEMENT OF ANY INTELLECTUAL PROPERTY RIGHTS, ANY
WARRANTIES ARISING BY USAGE OF TRADE, COURSE OF DEALING OR COURSE OF
PERFORMANCE, OR ANY WARRANTY THAT THE AT&T SOFTWARE IS "ERROR FREE" OR
WILL MEET YOUR REQUIREMENTS.

Unless you accept a license to use the AT&T Software, you shall not
reverse compile, disassemble or otherwise reverse engineer this
product to ascertain the source code for any AT&T Software.

(c) AT&T Corp. All rights reserved.  AT&T is a registered trademark of AT&T Corp.

***********************************************************************

History:

      27/12/2002 Hedzer Westra <hhwestra@cs.uu.nl>
*/

//********************************************************************
//********************************************************************

/* This module contains the base X compressors:
		binary	b
		hex		x
		hexcase	X	maintains case
		base64	base64

		extensions to other bases should be straightforward,
		although those will not be as efficient as possible
		(as is hexcase!) since the numbers will be parsed into
		unsigned int32 numbers. The total number can
		have an arbitrary number of digits. Negative numbers are
		not supported. A 0x or 0X prefix for hex(case) strings is
		maintained, zeros at the start as well.
 */

#include "stdafx.h"
#include <math.h>

/* constructor */
BaseXNumCompressor::BaseXNumCompressor(
		Session *s,
		unsigned long mymindigits,
		unsigned char b,
		unsigned char ishex
	  ): UserCompressor(s)
{
	Init(mymindigits, b, ishex);
}

void BaseXNumCompressor::Init(
			 unsigned long mymindigits,
  			 unsigned char b,
			 unsigned char ishex)
{
   mindigits=mymindigits;
   datasize=0;
	contnum=1;
	isrejecting=1;
	canoverlap=1;
	isfixedlen=0;
   base = b;
   preflag = 0;
	ishexcase = ishex;
	preskip = 0;
	if (base == 64) {
		/* we use only 24 bits (3 Bytes) */
		maxdigits = 4;
	} else {
		/* a hack to get 1<<32 without overflow.. */
		maxdigits = log(65536.0*65536.0) / log(base);
	}
}

/* helpers */
long BaseXNumCompressor::char2num(unsigned char c)
{
	long n;

	/* Note: base 63 and 65-255 are not supported */
	if (c < '0') {
		n = -1;
	} else if ((n = c - '0') > 10-1) {
		/* not numeric (0-9) */
		if (!ishexcase) {
			/* convert to upper case if not case sensitive */
			c = toupper(c);
		}
		if((n = c - 'A' + 10) > 10+26-1) {
			/* not upper case (10-35) */
			if((n = c - 'a' + 10 + 26) > 10+26+26-1) {
				/* not lower case (36-61) */
				n = -1;
			} else if (ishexcase && c < 'g') {
				/* hexcase is implemented using base-22 */
				n -= 'Z'-'G'+1;
			}
		}
	}

	/* check if within base limits */
	if (n >= base) {
		/* illegal char */
		n = -1;
	}

	return n;
}

long Base64Compressor::char2num(unsigned char c)
{
	long n;

	if (c < '0') {
		/* char should be skipped */
		n = 65;
	}
	if((n = c - 'A') > 26-1 || n < 0) {
		/* not upper case (0-25) */
		if((n = c - 'a' + 26) > 26+26-1 || n < 26) {
			/* not lower case (26-51) */
			if((n = c - '0' + 26 + 26) > 10+26+26-1 || n < 26+26) {
				/* not numeric (52-61) */
				switch (c) {
					case '+':
						n = 62;
						break;
					case '/':
						n = 63;
						break;
					case '=':
						/* padding */
						n = 64;
						break;
					default:
						/* char should be skipped */
						n = 65;
						break;
				}
			}
		}
	}
	return n;
}

/* checker / compressor */
char BaseXNumCompressor::ParseString(char *str,unsigned len,char *dataptr)
{
	unsigned int i = 0, j = 0;
	unsigned int num = 0;

	/* init flags & counters */
	preflag = 0;
	preskip = 0;
	numdigits = 0;

	/* check  for prefixes */
	if ((base == 16 || base == 22) && len>=XMILL_HEX_PREFIX_LEN) {
		if (!strncmp(str, XMILL_HEX_0x_STR, XMILL_HEX_PREFIX_LEN)) {
			preflag |= XMILL_HEX_0x;
			preskip = XMILL_HEX_PREFIX_LEN;
		} else if (!strncmp(str, XMILL_HEX_0X_STR, XMILL_HEX_PREFIX_LEN)) {
			preflag |= XMILL_HEX_0X;
			preskip = XMILL_HEX_PREFIX_LEN;
		}
	}
	/* check all digits and calculate compressed length */
	for (i=preskip; i<len; i++) {
		if ((num = char2num((unsigned char)str[i])) == -1)
			return FALSE;
		if (num < base && ++j == maxdigits) {
			j = 0;
			numdigits++;
		}
	}
	preflag |= j << XMILL_HEX_NUM_BITS;

	return TRUE;
}

void BaseXNumCompressor::CompressString(char *str,unsigned len,CompressContainer *cont,char *dataptr)
{
	unsigned long value = 0;
	unsigned int i = preskip, j = 0;

	/* store header */
	cont->StoreChar(preflag);
	cont->StoreUInt32(numdigits);

	/* store number */
	while (i<len) {
		value *= base;
		value += (unsigned long)char2num((unsigned char)str[i++]);
		if (++j == maxdigits) {
			/* flush */
		   cont->StoreUInt32(value);
			j = 0;
			value = 0;
		}
	}
	/* store trailing number */
	if (j > 0) {
		cont->StoreUInt32(value);
	}

#if 0
	/* store footer */
	postflag |= j;
	cont->StoreChar(postflag);
#endif
}

/* constructors */
BaseXNumUncompressor::BaseXNumUncompressor(): UserUncompressor()
{
}

BaseXNumUncompressor::BaseXNumUncompressor(
	 unsigned char b,
	 unsigned char ishex,
	 unsigned long mymindigits
   ): UserUncompressor()
{
	Init(b, ishex, mymindigits);
}

BaseXNumUncompressor::BaseXNumUncompressor(
	 Session *s,
 	 unsigned char b,
 	 unsigned char ishex,
	 unsigned long mymindigits
	): UserUncompressor(s)
{
	Init(b, ishex, mymindigits);
}

void BaseXNumUncompressor::Init(
		unsigned char b,
		unsigned char ishex,
		unsigned long mymindigits)
{
	mindigits=mymindigits;
   datasize=0;
	contnum=1;
   base = b;
   preflag = 0;
	ishexcase = ishex;
	if (base == 64) {
		/* we use only 24 bits (3 Bytes) */
		maxdigits = 4;
	} else {
		/* a hack to get 1<<32 without overflow.. */
		maxdigits = log(65536.0*65536.0) / log(base);
		startdiv = 1;
		for (int i=1; i<maxdigits; i++)
			startdiv *= base;
	}
}

unsigned char BaseXNumUncompressor::num2char(unsigned int n)
{
	if (n < 10) {
		return '0' + n;
	} else if (ishexcase && n>15) {
		return 'a' + n - 16;
	} else if (n < 26) {
		return 'A' + n - 10;
	} else if (n < 62) {
		return 'a' + n - 10 - 26;
	} else {
		return '?';
	}
}

/* uncompressor */
void BaseXNumUncompressor::UncompressItem(UncompressContainer *cont,char *dataptr,XMLOutput *xoutput)
{
	/* load header */
	preflag = (unsigned char)cont->LoadChar();
	numdigits = cont->LoadUInt32();
	restdigits = (preflag >> XMILL_HEX_NUM_BITS) & XMILL_BASEX_MAXDIGITS-1;

	/* prefix */
	if  ( (base == 16 || base == 22)
		 && preflag & XMILL_HEX_BITS) {
		if ((preflag & XMILL_HEX_BITS) == XMILL_HEX_0X) {
			xoutput->characters(XMILL_HEX_0X_STR, XMILL_HEX_PREFIX_LEN);
		} else if ((preflag & XMILL_HEX_BITS) == XMILL_HEX_0x) {
			xoutput->characters(XMILL_HEX_0x_STR, XMILL_HEX_PREFIX_LEN);
		}
	}

   /* prefix with zeros */
	unsigned int realdigits = numdigits * maxdigits + restdigits;
	if (mindigits > 0) {
		unsigned int extradigits = mindigits - realdigits;
		while (extradigits > 0) {
			realdigits = min(extradigits, sizeof(XMILL_ZEROS_STR)-1);
			xoutput->characters(XMILL_ZEROS_STR, realdigits);
			extradigits -= realdigits;
		}
	}

	/* print number */
	if (numdigits > 0 || restdigits > 0) {
		decodeNum (cont, xoutput);
	}
}

void BaseXNumUncompressor::decodeNum(UncompressContainer *cont, XMLOutput *xoutput)
{
	unsigned long value = 0;
	unsigned int len = 0;
	unsigned int div = 0;
	unsigned int curmaxdigits = maxdigits;

	while (numdigits > 0 || restdigits > 0) {
		/* load encoded number */
		value = cont->LoadUInt32();
		/* init counters etc */
		len = 0;
		if (numdigits == 0) {
			curmaxdigits = restdigits;
			restdigits = 0;
			div = 1;
			for (unsigned int i=1; i<curmaxdigits; i++)
				div *= base;
		} else {
			div = startdiv;
			numdigits--;
		}
		while (len < curmaxdigits) {
			/* decode number to a string */
			buffer[len++] = num2char(value / div);
			value %= div;
			div /= base;
		}

		/* output number */
		xoutput->characters((char*)buffer, len);

#if 0
		postflag = (unsigned char)cont->LoadChar();
#endif
	}
}

/* constructors for subclasses */
/* bin */
BinCompressor::BinCompressor(Session *s, unsigned long mymindigits):
	BaseXNumCompressor(s, mymindigits, 2, FALSE)
{}

BinUncompressor::BinUncompressor(unsigned long mymindigits):
	BaseXNumUncompressor(2, FALSE, mymindigits)
{}

BinUncompressor::BinUncompressor(Session *s, unsigned long mymindigits):
	BaseXNumUncompressor(s, 2, FALSE, mymindigits)
{}

/* hex */
HexCompressor::HexCompressor(Session *s, unsigned long mymindigits):
	BaseXNumCompressor(s, mymindigits, 16, FALSE)
{}

HexUncompressor::HexUncompressor(unsigned long mymindigits):
	BaseXNumUncompressor(16, FALSE, mymindigits)
{}

HexUncompressor::HexUncompressor(Session *s, unsigned long mymindigits):
	BaseXNumUncompressor(s, 16, FALSE, mymindigits)
{}

/* hexcase */
HexCaseCompressor::HexCaseCompressor(Session *s, unsigned long mymindigits):
	BaseXNumCompressor(s, mymindigits, 22, TRUE)
{}

HexCaseUncompressor::HexCaseUncompressor(unsigned long mymindigits):
	BaseXNumUncompressor(22, TRUE, mymindigits)
{}

HexCaseUncompressor::HexCaseUncompressor(Session *s, unsigned long mymindigits):
	BaseXNumUncompressor(s, 22, TRUE, mymindigits)
{}

/* base64 */
Base64Compressor::Base64Compressor(Session *s, unsigned long mymindigits):
	BaseXNumCompressor(s, mymindigits, 64, FALSE)
{}

Base64Uncompressor::Base64Uncompressor(unsigned long mymindigits):
	BaseXNumUncompressor(64, FALSE, mymindigits)
{}

Base64Uncompressor::Base64Uncompressor(Session *s, unsigned long mymindigits):
	BaseXNumUncompressor(s, 64, FALSE, mymindigits)
{}

/* base64 implementation */
void Base64Compressor::CompressString(char *str,unsigned len,CompressContainer *cont,char *dataptr)
{
	unsigned long value = 0, val = 0;
	unsigned int i = preskip, j = 0;

	/* store header */
	cont->StoreChar(preflag);
	cont->StoreUInt32(numdigits);

	/* store base64 string */
	while (i<len) {
		if (((val = (unsigned long)char2num((unsigned char)str[i++])) != -1)
			 && val < 64) {
			/* we skip invalid or padding chars, which should be done according to RFC 2045 */
			value <<= 6;
			value |= val;
			if (++j == 4) {
				/* flush 3 Bytes per 4 input Bytes (4*6 bits == 3*8 bits) */
				cont->StoreChar((unsigned char)(value>>16)&255);
				cont->StoreChar((unsigned char)(value>>8)&255);
				cont->StoreChar((unsigned char)value&255);
				j = 0;
				value = 0;
			}
		}
	}

	/* store extra chars */
	value <<= 6 * (4-j);
	if (j >= 1)
		cont->StoreChar((unsigned char)(value>>16)&255);
	if (j >= 2)
		cont->StoreChar((unsigned char)(value>>8)&255);
	if (j == 3)
		cont->StoreChar((unsigned char)value&255);

#if 0
	/* store footer */
	postflag |= j;
	cont->StoreChar(postflag);
#endif
}

unsigned char Base64Uncompressor::num2char(unsigned int c)
{
	if (c < 26) {
		return c + 'A';
	} else if (c < 52) {
		return c - 26 + 'a';
	} else if (c < 62) {
		return c - 52 + '0';
	} else if (c == 62) {
		return '+';
	} else if (c == 63) {
		return '/';
	} else {
		return '=';
	}
}

void Base64Uncompressor::decodeNum(UncompressContainer *cont, XMLOutput *xoutput)
{
	unsigned long value = 0;

	while (numdigits > 0 || restdigits > 0) {
		/* load 3 encoded Bytes */
		if (numdigits == 0) {
			value  = (((unsigned long)cont->LoadChar()) & 255) << 16;
			if (restdigits > 1)
				value |= (((unsigned long)cont->LoadChar()) & 255) << 8;
			if (restdigits > 2)
				value |= (unsigned long)cont->LoadChar() & 255;
		} else {
			value  = (((unsigned long)cont->LoadChar()) & 255) << 16;
			value |= (((unsigned long)cont->LoadChar()) & 255) << 8;
			value |= (unsigned long)cont->LoadChar() & 255;
		}

		buffer[0] = num2char((value >> 18) & 63);	// bits 23-18
		buffer[1] = num2char((value >> 12) & 63); // bits 17-12
		buffer[2] = num2char((value >> 6) & 63);	// bits 11-6
		buffer[3] = num2char(value & 63);			// bits 5-0

		/* is padding at the end needed ? */
		if (numdigits == 0) {
			for (unsigned int i=3; i>=restdigits; i--)
				buffer[i] = '=';
			restdigits = 0;
		} else {
			numdigits--;
		}

		/* output 4 base64 Bytes */
		xoutput->characters((char*)buffer, 4);

#if 0
		postflag = (unsigned char)cont->LoadChar();
#endif
	}
}

/* factories */
/* base-x */
char *BaseXNumCompressorFactory::GetName()
{
	return "basex";
}
char *BaseXNumCompressorFactory::GetDescription()
{
	return "Compressor for arbitrary-length arbitrary-base numbers";
}

UserCompressor *BaseXNumCompressorFactory::InstantiateCompressor(char *paramstr,int len)
{
   unsigned long mindigits = 0;
	unsigned char base = 10;
	char *str = NULL;

   if (paramstr) {
		/* NULL-terminate parameter string */
      char savechar = paramstr[len];
      paramstr[len]= '\0';
		/* check for second argument */
		str = strstr(paramstr, " ");
		/* parse first (==base) */
      base = atoi(paramstr);
		/* parse second (==mindigits) */
		if (str && str[0]) {
	      mindigits = atoi(str+1);
		}
		/* fix paramstr */
      paramstr[len] = savechar;
		/* check base */
      if(base <= 0) {
         XMillException *e = new XMillException(XMILL_ERR_ARGUMENTS, "Invalid parameter '");
         e->ErrorCont(paramstr,len);
         e->ErrorCont("' for compressor 'basex'!");
         throw e;
      }
   }
   return new BaseXNumCompressor(session, mindigits, base, false);
}

UserUncompressor *BaseXNumCompressorFactory::InstantiateUncompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
	unsigned char base = 10;
	char *str = NULL;

	if (paramstr) {
		/* NULL-terminate parameter string */
      char savechar = paramstr[len];
      paramstr[len]= '\0';
		/* check for second argument */
		str = strstr(paramstr, " ");
		/* parse first (==base) */
      base = atoi(paramstr);
		/* parse second (==mindigits) */
		if (str && str[0]) {
	      mindigits = atoi(str+1);
		}
		/* fix paramstr */
      paramstr[len] = savechar;
      return new BaseXNumUncompressor(session, base, FALSE, mindigits);
	} else {
      return &uncompressor;
	}
}

/* hex */
char *HexCompressorFactory::GetName()
{
	return "x";
}
char *HexCompressorFactory::GetDescription()
{
	return "Compressor for large hex numbers";
}

UserCompressor *HexCompressorFactory::InstantiateCompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      if(mindigits<=0)
      {
         XMillException *e = new XMillException(XMILL_ERR_ARGUMENTS, "Invalid parameter '");
         e->ErrorCont(paramstr,len);
         e->ErrorCont("' for compressor 'x'!");
         throw e;
      }
   }
   return new HexCompressor(session, mindigits);
}

UserUncompressor *HexCompressorFactory::InstantiateUncompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      return new HexUncompressor(session, mindigits);
   }
   else
      return &uncompressor;
}

/* hex-case */
char *HexCaseCompressorFactory::GetName()
{
	return "X";
}
char *HexCaseCompressorFactory::GetDescription()
{
	return "Compressor for case sensitive large hex numbers";
}

UserCompressor *HexCaseCompressorFactory::InstantiateCompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      if(mindigits<=0)
      {
         XMillException *e = new XMillException(XMILL_ERR_ARGUMENTS, "Invalid parameter '");
         e->ErrorCont(paramstr,len);
         e->ErrorCont("' for compressor 'X'!");
         throw e;
      }
   }
   return new HexCaseCompressor(session, mindigits);
}

UserUncompressor *HexCaseCompressorFactory::InstantiateUncompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      return new HexCaseUncompressor(session, mindigits);
   }
   else
      return &uncompressor;
}

/* binary */
char *BinCompressorFactory::GetName()
{
	return "b";
}
char *BinCompressorFactory::GetDescription()
{
	return "Compressor for large binary numbers";
}

UserCompressor *BinCompressorFactory::InstantiateCompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      if(mindigits<=0)
      {
         XMillException *e = new XMillException(XMILL_ERR_ARGUMENTS, "Invalid parameter '");
         e->ErrorCont(paramstr,len);
         e->ErrorCont("' for compressor 'b'!");
         throw e;
      }
   }
   return new BinCompressor(session, mindigits);
}

UserUncompressor *BinCompressorFactory::InstantiateUncompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      return new BinUncompressor(session, mindigits);
   }
   else
      return &uncompressor;
}

/* base64 */
char *Base64CompressorFactory::GetName()
{
	return "base64";
}
char *Base64CompressorFactory::GetDescription()
{
	return "Compressor for base64 encoded strings";
}

UserCompressor *Base64CompressorFactory::InstantiateCompressor(char *paramstr,int len)
{
   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      throw new XMillException(XMILL_ERR_ARGUMENTS,
			"base64 does not accept any parameters!");
/*      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      if(mindigits<=0)
      {
         XMillException *e = new XMillException(XMILL_ERR_ARGUMENTS, "Invalid parameter '");
         e->ErrorCont(paramstr,len);
         e->ErrorCont("' for compressor 'x'!");
         throw e;
      }*/
   }
   return new Base64Compressor(session, mindigits);
}

UserUncompressor *Base64CompressorFactory::InstantiateUncompressor(char *paramstr,int len)
{
/*   unsigned long mindigits=0;
   if(paramstr!=NULL)
   {
      char savechar=paramstr[len];
      paramstr[len]=0;
      mindigits=atoi(paramstr);
      paramstr[len]=savechar;
      return new Base64Uncompressor(session, mindigits);
   }
   else*/
      return &uncompressor;
}