Rockboy - gameboy emulation for rockbox, based on gnuboy. Still a bit early, but already playable on iRiver H1xx and the simulators. The archos recorder version is currently rather slow...

git-svn-id: svn://svn.rockbox.org/rockbox/trunk@6104 a1c6a512-1295-4272-9138-f99709370657

1 files changed, 514 insertions, 0 deletions

diff --git a/apps/plugins/rockboy/inflate.c b/apps/plugins/rockboy/inflate.c
new file mode 100644
index 0000000..6818749
--- /dev/null
+++ b/apps/plugins/rockboy/inflate.c
@@ -0,0 +1,514 @@
+
+/* Slightly modified from its original form so as not to exit the
+ * program on errors. The resulting file remains in the public
+ * domain for all to use. */
+
+/* --- GZIP file format uncompression routines --- */
+
+/* The following routines (notably the unzip()) function below
+ * uncompress gzipped data.  They are terribly slow at the task, but
+ * it is presumed that they work reasonably well.  They don't do any
+ * error checking, but they're probably not too vulnerable to buggy
+ * data either.  Another important limitation (but it would be pretty
+ * easy to get around) is that the data must reside in memory, it is
+ * not read as a stream.  They have been very little tested.  Anyway,
+ * whatever these functions are good for, I put them in the public
+ * domain.  -- David Madore <david.madore@ens.fr> 1999/11/21 */
+
+#include "rockmacros.h"
+
+static unsigned int
+peek_bits (const unsigned char *data, long p, int q)
+     /* Read q bits starting from bit p from the data pointed to by
+      * data.  Data is in little-endian format. */
+{
+  unsigned int answer;
+  int cnt; /* Number of bits already placed in answer */
+  char ob, lb; /* Offset and length of bit field within current byte */
+
+  answer = 0;
+  for ( cnt=0 ; cnt<q ; /* cnt updated in body */ )
+    {
+      ob = (p+cnt)%8;
+      lb = 8-ob;
+      if ( cnt+lb > q )
+	lb = q-cnt;
+      answer |= ((unsigned int)((data[(p+cnt)/8]>>ob)&((1U<<lb)-1)))<<cnt;
+      cnt += lb;
+    }
+  return answer;
+}
+
+static unsigned int
+read_bits (const unsigned char *data, long *p, int q)
+     /* Read q bits as per peek_bits(), but also increase p by q. */
+{
+  unsigned int answer;
+
+  answer = peek_bits (data, *p, q);
+  *p += q;
+  return answer;
+}
+
+static void
+make_code_table (const char size_table[], int table_length,
+		 unsigned int code_table[], int maxbits)
+     /* Make a code table from a length table.  See rfc1951, section
+      * 3.2.2, for details on what this means.  The size_table
+      * contains the length of the Huffman codes for each letter, and
+      * the code_table receives the computed codes themselves.
+      * table_length is the size of the tables (alphabet length) and
+      * maxbits is the maximal allowed code length. */
+{
+  int i, j;
+  unsigned int code;
+
+  code = 0;
+  for ( i=1 ; i<=maxbits ; i++ )
+    {
+      for ( j=0 ; j<table_length ; j++ )
+	{
+	  if ( size_table[j]==i )
+	    code_table[j] = code++;
+	}
+      code <<= 1;
+    }
+}
+
+static int
+decode_one (const unsigned char *data, long *p,
+	    const char size_table[], int table_length,
+	    const unsigned int code_table[], int maxbits)
+     /* Decode one alphabet letter from the data, starting at bit p
+      * (which will be increased by the appropriate amount) using
+      * size_table and code_table to decipher the Huffman encoding. */
+{
+  unsigned int code;
+  int i, j;
+
+  code = 0;
+  /* Read as many bits as are likely to be necessary - backward, of
+   * course. */
+  for ( i=0 ; i<maxbits ; i++ )
+    code = (code<<1) + peek_bits (data, (*p)+i, 1);
+  /* Now examine each symbol of the table to find one that matches the
+   * first bits of the code read. */
+  for ( j=0 ; j<table_length ; j++ )
+    {
+      if ( size_table[j]
+	   && ( (code>>(maxbits-size_table[j])) == code_table[j] ) )
+	{
+	  *p += size_table[j];
+	  return j;
+	}
+    }
+  return -1;
+}
+
+/* I don't know what these should be.  The rfc1951 doesn't seem to say
+ * (it only mentions them in the last paragraph of section 3.2.1).  15
+ * is almost certainly safe, and it is the largest I can put given the
+ * constraints on the size of integers in the C standard. */
+#define CLEN_MAXBITS 15
+#define HLIT_MAXBITS 15
+#define HDIST_MAXBITS 15
+
+/* The magical table sizes... */
+#define CLEN_TSIZE 19
+#define HLIT_TSIZE 288
+#define HDIST_TSIZE 30
+
+static int
+get_tables (const unsigned char *data, long *p,
+	    char hlit_size_table[HLIT_TSIZE],
+	    unsigned int hlit_code_table[HLIT_TSIZE],
+	    char hdist_size_table[HDIST_TSIZE],
+	    unsigned int hdist_code_table[HDIST_TSIZE])
+     /* Fill the Huffman tables (first the code lengths table, and
+      * then, using it, the literal/length table and the distance
+      * table).  See section 3.2.7 of rfc1951 for details. */
+{
+  char hlit, hdist, hclen;
+  const int clen_weird_tangle[CLEN_TSIZE]
+    = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
+  char clen_size_table[CLEN_TSIZE];
+  unsigned int clen_code_table[CLEN_TSIZE];
+  int j;
+  unsigned int b;
+  int remainder; /* See note at end of section 3.2.7 of rfc1951. */
+  char rem_val;
+
+  hlit = read_bits (data, p, 5);
+  hdist = read_bits (data, p, 5);
+  hclen = read_bits (data, p, 4);
+  for ( j=0 ; j<4+hclen ; j++ )
+    clen_size_table[clen_weird_tangle[j]]
+      = read_bits (data, p, 3);
+  for ( ; j<CLEN_TSIZE ; j++ )
+    clen_size_table[clen_weird_tangle[j]] = 0;
+  make_code_table (clen_size_table, CLEN_TSIZE,
+		   clen_code_table, CLEN_MAXBITS);
+  remainder = 0;
+  rem_val = 0;
+  for ( j=0 ; j<257+hlit ; j++ )
+    {
+      b = decode_one (data, p, clen_size_table, CLEN_TSIZE,
+		      clen_code_table, CLEN_MAXBITS);
+      if ( b<0 ) return -1;
+      if ( b<16 )
+	hlit_size_table[j] = b;
+      else if ( b == 16 )
+	{
+	  int k, l;
+
+	  k = read_bits (data, p, 2);
+	  for ( l=0 ; l<k+3 && j+l<257+hlit ; l++ )
+	    hlit_size_table[j+l] = hlit_size_table[j-1];
+	  j += l-1;
+	  remainder = k+3-l; /* THIS IS SO UGLY! */
+	  rem_val = hlit_size_table[j-1];
+	}
+      else if ( b == 17 )
+	{
+	  int k, l;
+
+	  k = read_bits (data, p, 3);
+	  for ( l=0 ; l<k+3 && j+l<257+hlit ; l++ )
+	    hlit_size_table[j+l] = 0;
+	  j += l-1;
+	  remainder = k+3-l;
+	  rem_val = 0;
+	}
+      else if ( b == 18 )
+	{
+	  int k, l;
+
+	  k = read_bits (data, p, 7);
+	  for ( l=0 ; l<k+11 && j+l<257+hlit ; l++ )
+	    hlit_size_table[j+l] = 0;
+	  j += l-1;
+	  remainder = k+11-l;
+	  rem_val = 0;
+	}
+    }
+  for ( ; j<HLIT_TSIZE ; j++ )
+    hlit_size_table[j] = 0;
+  make_code_table (hlit_size_table, HLIT_TSIZE,
+		   hlit_code_table, HLIT_MAXBITS);
+  for ( j=0 ; j<remainder ; j++ )
+    hdist_size_table[j] = rem_val;
+  for ( ; j<1+hdist ; j++ )
+    /* Can you spell: ``copy-paste''? */
+    {
+      b = decode_one (data, p, clen_size_table, CLEN_TSIZE,
+		      clen_code_table, CLEN_MAXBITS);
+      if ( b<0 ) return -1;
+      if ( b<16 )
+	hdist_size_table[j] = b;
+      else if ( b == 16 )
+	{
+	  int k, l;
+
+	  k = read_bits (data, p, 2);
+	  for ( l=0 ; l<k+3 && j+l<1+hdist ; l++ )
+	    hdist_size_table[j+l] = hdist_size_table[j-1];
+	  j += l-1;
+	}
+      else if ( b == 17 )
+	{
+	  int k, l;
+
+	  k = read_bits (data, p, 3);
+	  for ( l=0 ; l<k+3 && j+l<1+hdist ; l++ )
+	    hdist_size_table[j+l] = 0;
+	  j += l-1;
+	}
+      else if ( b == 18 )
+	{
+	  int k, l;
+
+	  k = read_bits (data, p, 7);
+	  for ( l=0 ; l<k+11 && j+l<1+hdist ; l++ )
+	    hdist_size_table[j+l] = 0;
+	  j += l-1;
+	}
+    }
+  for ( ; j<HDIST_TSIZE ; j++ )
+    hdist_size_table[j] = 0;
+  make_code_table (hdist_size_table, HDIST_TSIZE,
+		   hdist_code_table, HDIST_MAXBITS);
+  return 0;
+}
+
+/* The (circular) output buffer.  This lets us track
+ * backreferences. */
+
+/* Minimal buffer size.  Also the only useful value. */
+#define BUFFER_SIZE 32768
+
+/* Pointer to the character to be added to the buffer */
+static unsigned int buffer_ptr = 0;
+
+/* The buffer itself */
+static unsigned char buffer[BUFFER_SIZE];
+
+static void
+pushout (unsigned char ch)
+     /* Store one byte in the output buffer so it may be retrieved if
+      * it is referenced again. */
+{
+  buffer[buffer_ptr++] = ch;
+  buffer_ptr %= BUFFER_SIZE;
+}
+
+static unsigned char
+pushin (unsigned int dist)
+     /* Retrieve one byte, dist bytes away, from the output buffer. */
+{
+  return buffer[(buffer_ptr+(BUFFER_SIZE-dist))%BUFFER_SIZE];
+}
+
+static int
+get_data (const unsigned char *data, long *p,
+	  const char hlit_size_table[HLIT_TSIZE],
+	  const unsigned int hlit_code_table[HLIT_TSIZE],
+	  const char hdist_size_table[HDIST_TSIZE],
+	  const unsigned int hdist_code_table[HDIST_TSIZE],
+	  void (* callback) (unsigned char d))
+     /* Do the actual uncompressing.  Call callback on each character
+      * uncompressed. */
+{
+  unsigned int b;
+
+  while ( 1 ) {
+    b = decode_one (data, p, hlit_size_table, HLIT_TSIZE,
+		    hlit_code_table, HLIT_MAXBITS);
+    if ( b<0 ) return -1;
+    if ( b < 256 )
+      /* Literal */
+      {
+	pushout ((unsigned char) b);
+	callback ((unsigned char) b);
+      }
+    else if ( b == 256 )
+      /* End of block */
+      return 0;
+    else if ( b >= 257 )
+      /* Back reference */
+      {
+	unsigned int bb;
+	unsigned int length, dist;
+	unsigned int l;
+
+	switch ( b )
+	  {
+	  case 257: length = 3; break;
+	  case 258: length = 4; break;
+	  case 259: length = 5; break;
+	  case 260: length = 6; break;
+	  case 261: length = 7; break;
+	  case 262: length = 8; break;
+	  case 263: length = 9; break;
+	  case 264: length = 10; break;
+	  case 265: length = 11 + read_bits (data, p, 1); break;
+	  case 266: length = 13 + read_bits (data, p, 1); break;
+	  case 267: length = 15 + read_bits (data, p, 1); break;
+	  case 268: length = 17 + read_bits (data, p, 1); break;
+	  case 269: length = 19 + read_bits (data, p, 2); break;
+	  case 270: length = 23 + read_bits (data, p, 2); break;
+	  case 271: length = 27 + read_bits (data, p, 2); break;
+	  case 272: length = 31 + read_bits (data, p, 2); break;
+	  case 273: length = 35 + read_bits (data, p, 3); break;
+	  case 274: length = 43 + read_bits (data, p, 3); break;
+	  case 275: length = 51 + read_bits (data, p, 3); break;
+	  case 276: length = 59 + read_bits (data, p, 3); break;
+	  case 277: length = 67 + read_bits (data, p, 4); break;
+	  case 278: length = 83 + read_bits (data, p, 4); break;
+	  case 279: length = 99 + read_bits (data, p, 4); break;
+	  case 280: length = 115 + read_bits (data, p, 4); break;
+	  case 281: length = 131 + read_bits (data, p, 5); break;
+	  case 282: length = 163 + read_bits (data, p, 5); break;
+	  case 283: length = 195 + read_bits (data, p, 5); break;
+	  case 284: length = 227 + read_bits (data, p, 5); break;
+	  case 285: length = 258; break;
+	  default:
+	    return -1;
+	  }
+	bb = decode_one (data, p, hdist_size_table, HDIST_TSIZE,
+			 hdist_code_table, HDIST_MAXBITS);
+	switch ( bb )
+	  {
+	  case 0: dist = 1; break;
+	  case 1: dist = 2; break;
+	  case 2: dist = 3; break;
+	  case 3: dist = 4; break;
+	  case 4: dist = 5 + read_bits (data, p, 1); break;
+	  case 5: dist = 7 + read_bits (data, p, 1); break;
+	  case 6: dist = 9 + read_bits (data, p, 2); break;
+	  case 7: dist = 13 + read_bits (data, p, 2); break;
+	  case 8: dist = 17 + read_bits (data, p, 3); break;
+	  case 9: dist = 25 + read_bits (data, p, 3); break;
+	  case 10: dist = 33 + read_bits (data, p, 4); break;
+	  case 11: dist = 49 + read_bits (data, p, 4); break;
+	  case 12: dist = 65 + read_bits (data, p, 5); break;
+	  case 13: dist = 97 + read_bits (data, p, 5); break;
+	  case 14: dist = 129 + read_bits (data, p, 6); break;
+	  case 15: dist = 193 + read_bits (data, p, 6); break;
+	  case 16: dist = 257 + read_bits (data, p, 7); break;
+	  case 17: dist = 385 + read_bits (data, p, 7); break;
+	  case 18: dist = 513 + read_bits (data, p, 8); break;
+	  case 19: dist = 769 + read_bits (data, p, 8); break;
+	  case 20: dist = 1025 + read_bits (data, p, 9); break;
+	  case 21: dist = 1537 + read_bits (data, p, 9); break;
+	  case 22: dist = 2049 + read_bits (data, p, 10); break;
+	  case 23: dist = 3073 + read_bits (data, p, 10); break;
+	  case 24: dist = 4097 + read_bits (data, p, 11); break;
+	  case 25: dist = 6145 + read_bits (data, p, 11); break;
+	  case 26: dist = 8193 + read_bits (data, p, 12); break;
+	  case 27: dist = 12289 + read_bits (data, p, 12); break;
+	  case 28: dist = 16385 + read_bits (data, p, 13); break;
+	  case 29: dist = 24577 + read_bits (data, p, 13); break;
+	  default:
+            return -1;
+	  }
+	for ( l=0 ; l<length ; l++ )
+	  {
+	    unsigned char ch;
+
+	    ch = pushin (dist);
+	    pushout (ch);
+	    callback (ch);
+	  }
+      }
+  }
+  return 0;
+}
+
+static int
+inflate (const unsigned char *data, long *p,
+	 void (* callback) (unsigned char d))
+     /* Main uncompression function for the deflate method */
+{
+  char blast, btype;
+  char hlit_size_table[HLIT_TSIZE];
+  unsigned int hlit_code_table[HLIT_TSIZE];
+  char hdist_size_table[HDIST_TSIZE];
+  unsigned int hdist_code_table[HDIST_TSIZE];
+
+ again:
+  blast = read_bits (data, p, 1);
+  btype = read_bits (data, p, 2);
+  if ( btype == 1 || btype == 2 )
+    {
+      if ( btype == 2 )
+        {
+	  /* Dynamic Huffman tables */
+	  if (get_tables (data, p,
+		          hlit_size_table, hlit_code_table,
+		          hdist_size_table, hdist_code_table) < 0) return -1;
+	}
+      else
+	/* Fixed Huffman codes */
+	{
+	  int j;
+
+	  for ( j=0 ; j<144 ; j++ )
+	    hlit_size_table[j] = 8;
+	  for ( ; j<256 ; j++ )
+	    hlit_size_table[j] = 9;
+	  for ( ; j<280 ; j++ )
+	    hlit_size_table[j] = 7;
+	  for ( ; j<HLIT_TSIZE ; j++ )
+	    hlit_size_table[j] = 8;
+	  make_code_table (hlit_size_table, HLIT_TSIZE,
+			   hlit_code_table, HLIT_MAXBITS);
+	  for ( j=0 ; j<HDIST_TSIZE ; j++ )
+	    hdist_size_table[j] = 5;
+	  make_code_table (hdist_size_table, HDIST_TSIZE,
+			   hdist_code_table, HDIST_MAXBITS);
+	}
+      if (get_data (data, p,
+		    hlit_size_table, hlit_code_table,
+		    hdist_size_table, hdist_code_table,
+		    callback) < 0) return -1;;
+    }
+  else if ( btype == 0 )
+    /* Non compressed block */
+    {
+      unsigned int len, nlen;
+      unsigned int l;
+      unsigned char b;
+
+      *p = (*p+7)/8; /* Jump to next byte boundary */
+      len = read_bits (data, p, 16);
+      nlen = read_bits (data, p, 16);
+      for ( l=0 ; l<len ; l++ )
+	{
+	  b = read_bits (data, p, 8);
+	  pushout (b);
+	  callback (b);
+	}
+    }
+  else
+    {
+      return -1;
+    }
+  if ( ! blast )
+    goto again;
+  return 0;
+}
+
+int
+unzip (const unsigned char *data, long *p,
+       void (* callback) (unsigned char d))
+     /* Uncompress gzipped data.  data is a pointer to the data, p is
+      * a pointer to a long that is initialized to 0 (unless for some
+      * reason you want to start uncompressing further down the data),
+      * and callback is a function taking an unsigned char and
+      * returning void that will be called successively for every
+      * uncompressed byte. */
+{
+  unsigned char cm, flg;
+
+  if ( read_bits (data, p, 8) != 0x1f
+       || read_bits (data, p, 8) != 0x8b )
+    {
+      return -1;
+    }
+  cm = read_bits (data, p, 8);
+  if ( cm != 0x8 )
+    {
+      return -1;
+    }
+  flg = read_bits (data, p, 8);
+  if ( flg & 0xe0 )
+    /* fprintf (stderr, "Warning: unknown bits are set in flags.\n") */ ;
+  read_bits (data, p, 32); /* Ignore modification time */
+  read_bits (data, p, 8); /* Ignore extra flags */
+  read_bits (data, p, 8); /* Ignore OS type */
+  if ( flg & 0x4 )
+    {
+      /* Skip over extra data */
+      unsigned int xlen;
+
+      xlen = read_bits (data, p, 16);
+      *p += ((long)xlen)*8;
+    }
+  if ( flg & 0x8 )
+    {
+      /* Skip over file name */
+      while ( read_bits (data, p, 8) );
+    }
+  if ( flg & 0x10 )
+    {
+      /* Skip over comment */
+      while ( read_bits (data, p, 8) );
+    }
+  if ( flg & 0x2 )
+    /* Ignore CRC16 */
+    read_bits (data, p, 16);
+  return inflate (data, p, callback);
+  /* CRC32 and ISIZE are at the end.  We don't even bother to look at
+   * them. */
+}
+