1 files changed, 132 insertions, 0 deletions
diff --git a/ext/tarkin/golomb.h b/ext/tarkin/golomb.h
new file mode 100644
index 00000000..fa66d750
--- /dev/null
+++ b/ext/tarkin/golomb.h
@@ -0,0 +1,132 @@
+#ifndef __GOLOMB_H
+#define __GOLOMB_H
+
+
+#include "bitcoder.h"
+
+
+static inline
+unsigned int required_bits (unsigned int x)
+{
+   int bits = 31;
+
+   while ((x & (1 << bits)) == 0 && bits)
+      bits--;
+
+   return bits;
+}
+
+
+static inline
+void write_number_binary (BitCoderState *b, unsigned int x, int bits, int u)
+{
+//printf ("wrote %i with %i bits (%i+%i)\n", x, u+bits, u, bits);
+   while (bits) {
+      bits--;
+      bitcoder_write_bit (b, (x >> bits) & 1);
+   }
+}
+
+
+static inline
+unsigned int read_number_binary (BitCoderState *b, int bits)
+{
+   unsigned int x = 0;
+
+   while (bits) {
+      bits--;
+      x |= bitcoder_read_bit (b) << bits;
+   }
+
+   return x;
+}
+
+
+static inline
+void golomb_write_number (BitCoderState *b, unsigned int x, int bits)
+{
+   unsigned int q, r;
+int i = 0;
+
+   assert (x > 0);
+
+   while ((q = (x - 1) >> bits) > 0) {
+      bitcoder_write_bit (b, 1);   /* fast temporary adaption, write  */ 
+      bits++;                      /* unary representation of q       */
+i++;
+   };
+
+   bitcoder_write_bit (b, 0);
+
+   r = x - 1 - (q << bits); 
+
+   write_number_binary (b, r, bits, i+1);
+}
+
+
+static inline
+unsigned int golomb_read_number (BitCoderState *b, int bits)
+{
+   unsigned int q = 0, r, x;
+
+   while (bitcoder_read_bit (b) != 0) {
+      bits++;
+   }
+
+   r = read_number_binary (b, bits);
+   x = (q << bits) + r + 1;
+
+   return x;
+}
+
+
+typedef struct {
+   uint8_t count;
+   uint8_t bits;          /* a 5.3 fixed point integer  */
+} GolombAdaptiveCoderState;
+
+#define GOLOMB_ADAPTIVE_CODER_STATE_INITIALIZER { 8<<3, 0 }
+
+
+static const int golomb_w_tab [] = { 256, 128, 64 };
+
+
+
+
+static inline
+void golombcoder_encode_number (GolombAdaptiveCoderState *g,
+                                BitCoderState *b,
+                                unsigned int x)
+{
+   golomb_write_number (b, x, g->bits >> 3);
+
+   g->bits = ((256 - golomb_w_tab[g->count]) * (int) g->bits +
+                     golomb_w_tab[g->count] * (required_bits(x)<<3)) / 256;
+   g->count++;
+
+   if (g->count > 2)
+      g->count = 2;
+}
+
+
+static inline
+unsigned int golombcoder_decode_number (GolombAdaptiveCoderState *g,
+                                        BitCoderState *b)
+{
+   unsigned int x;
+
+   x = golomb_read_number (b, g->bits >> 3);
+
+   g->bits = ((256 - golomb_w_tab[g->count]) * g->bits + 
+                     golomb_w_tab[g->count] * (required_bits(x)<<3)) / 256;
+   g->count++;
+
+   if (g->count > 2)
+      g->count = 2;
+
+   return x;
+}
+
+
+#endif
+