Sunday, June 9, 2013

Best book review - Elements of Electromagnetics

Elements of Electromagnetics: Matthew N. O. Sadiku: 9780199743001: Amazon.com: Books: This book teaches electromagnetics and baldness. The latter comes from tearing out ones hair looking for the problem in ones work that doesn't actually exist, but does exist in the solutions you are comparing your work to.
Two stars because the book functions nicely as a club and projectile.

Friday, November 9, 2012

Who's a good programmer?

A smart accountant once told me that the answer to "How much money did you make?" is always, "Who wants to know?" If it's an investor, the answer is "A lot." If it's a customer, the answer is "A little." If it's the IRS, the answer is "None."
Same thing here. The answer to "Who is a good programmer?" is always, "Who wants to know?"
Read the rest of the post. Interesting discussion as always

Tuesday, October 2, 2012

Cross-compile nginx 1.3.6

The following adds support for cross compiling nginx. You need SSH access to your system to run the tests. It's not a complete patch because it still looks locally for headers and such.

Wednesday, September 26, 2012

On exceptions

I've been reading some blog posts on exceptions recently. The one I hadn't seen before, and the one that makes a lot of sense to me is:

Cleaner, more elegant, and harder to recognize

The argument put forward is that yes, using exceptions does make for cleaner code, but

  1. It's easier to write bad code that uses exceptions
  2. It's harder to recognize good code from bad code when using exceptions
The D language has an interesting scope guard statement. Not having played with this, I don't know what the ramifications are in practice. I haven't used this in C++. I wonder how ugly the code gets?

Monday, September 10, 2012

Disks lie

Disks lie. And the controllers that run them are partners in crime. | Hacker News:
The behavior of hard drives is like decaying atoms. You can't make accurate predictions about what any one of them will do. Only in aggregate can you say something like "the half life of this pile of hardware is 12 years" or "if we write this data N times we can reasonably expect to read it it again."

Monday, August 13, 2012

The Art of Computer Programming, Volume 5

The Art of Computer Programming:

Syntactic Algorithms, in preparation. 
9. Lexical scanning (includes also string search and data compression)
10. Parsing techniques 
Estimated to be ready in 2020.
What a schedule.

Wednesday, July 25, 2012

Modifying gzip to only do huffman coding

Recently I needed to compress certain types of files on a system with very limited memory. After looking at LZ77, LZ78, and derivatives I chose simple huffman coding as it gave me ~50% savings on the file, with limited resources.

The first possible candidate was http://entropyware.info/shcodec/index.html

In the end, I modified gzip to output only huffman compressed data. I modified puff.c (included with zlib) to only care about these types of blocks.

Patch to zlib

--- ../gzip-1.4-orig/deflate.c  2010-01-03 12:26:02.000000000 -0500
+++ deflate.c   2012-07-25 11:47:30.000000000 -0400
@@ -673,8 +673,11 @@ off_t deflate()
     int flush;               /* set if current block must be flushed */
     int match_available = 0; /* set if previous match exists */
     register unsigned match_length = MIN_MATCH-1; /* length of best match */
+    extern int huffonly;       /* gzip.c */

+    if (huffonly == 0) {
     if (compr_level <= 3) return deflate_fast(); /* optimized for speed */
+    }

     /* Process the input block. */
     while (lookahead != 0) {
@@ -690,7 +693,8 @@ off_t deflate()

         if (hash_head != NIL && prev_length < max_lazy_match &&
             strstart - hash_head <= MAX_DIST &&
-            strstart <= window_size - MIN_LOOKAHEAD) {
+            strstart <= window_size - MIN_LOOKAHEAD &&
+           huffonly==0) {
             /* To simplify the code, we prevent matches with the string
              * of window index 0 (in particular we have to avoid a match
              * of the string with itself at the start of the input file).
@@ -710,7 +714,8 @@ off_t deflate()
         /* If there was a match at the previous step and the current
          * match is not better, output the previous match:
          */
-        if (prev_length >= MIN_MATCH && match_length <= prev_length) {
+        if (prev_length >= MIN_MATCH && match_length <= prev_length
+               && huffonly==0) {

             check_match(strstart-1, prev_match, prev_length);

--- ../gzip-1.4-orig/gzip.c     2010-01-03 12:26:02.000000000 -0500
+++ gzip.c      2012-07-25 11:53:29.000000000 -0400
@@ -194,6 +194,7 @@ char *env;            /* contents of GZI
 char **args = NULL;   /* argv pointer if GZIP env variable defined */
 char const *z_suffix; /* default suffix (can be set with --suffix) */
 size_t z_len;         /* strlen(z_suffix) */
+int huffonly = 0;   /* only use huffman codes, no LZ77 */

 /* The set of signals that are caught.  */
 static sigset_t caught_signals;
@@ -271,6 +272,7 @@ struct option longopts[] =
     {"best",       0, 0, '9'}, /* compress better */
     {"lzw",        0, 0, 'Z'}, /* make output compatible with old compress */
     {"bits",       1, 0, 'b'}, /* max number of bits per code (implies -Z) */
+    {"huffonly",   0, 0, 'O'}, /* ascii text mode */
     { 0, 0, 0, 0 }
 };

@@ -352,6 +354,7 @@ local void help()
  "  -Z, --lzw         produce output compatible with old compress",
  "  -b, --bits=BITS   max number of bits per code (implies -Z)",
 #endif
+ "  -O, --huffonly    only compress using dynamic huffman codes (block type 2)",
  "",
  "With no FILE, or when FILE is -, read standard input.",
  "",
@@ -502,6 +505,9 @@ int main (int argc, char **argv)
            try_help ();
            break;
 #endif
+       case 'O':
+           huffonly = 1;
+           break;
        case '1':  case '2':  case '3':  case '4':
        case '5':  case '6':  case '7':  case '8':  case '9':
            level = optc - '0';     

Changes to puff.c

--- puff.orig.c 2010-04-25 05:04:16.000000000 -0400
+++ puff.new.c  2012-07-25 13:33:16.000000000 -0400
@@ -160,6 +160,7 @@ local int bits(struct state *s, int need
  * - A stored block can have zero length.  This is sometimes used to byte-align
  *   subsets of the compressed data for random access or partial recovery.
  */
+#ifndef CONFIG_ONLY_BLOCK_2
 local int stored(struct state *s)
 {
     unsigned len;       /* length of stored block */
@@ -194,6 +195,7 @@ local int stored(struct state *s)
     /* done with a valid stored block */
     return 0;
 }
+#endif

 /*
  * Huffman code decoding tables.  count[1..MAXBITS] is the number of symbols of
@@ -437,6 +439,7 @@ local int codes(struct state *s,
                 const struct huffman *distcode)
 {
     int symbol;         /* decoded symbol */
+#ifndef CONFIG_ONLY_BLOCK_2
     int len;            /* length for copy */
     unsigned dist;      /* distance for copy */
     static const short lens[29] = { /* Size base for length codes 257..285 */
@@ -453,6 +456,7 @@ local int codes(struct state *s,
         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
         12, 12, 13, 13};
+#endif

     /* decode literals and length/distance pairs */
     do {
@@ -469,6 +473,10 @@ local int codes(struct state *s,
             s->outcnt++;
         }
         else if (symbol > 256) {        /* length */
+#ifdef CONFIG_ONLY_BLOCK_2
+           /* I never put out anything but literals */
+           return -11;
+#else /* CONFIG_ONLY_BLOCK_2 */
             /* get and compute length */
             symbol -= 257;
             if (symbol >= 29)
@@ -501,6 +509,7 @@ local int codes(struct state *s,
             }
             else
                 s->outcnt += len;
+#endif /* CONFIG_ONLY_BLOCK_2 */
         }
     } while (symbol != 256);            /* end of block symbol */

@@ -532,6 +541,7 @@ local int codes(struct state *s,
  *   length, this can be implemented as an incomplete code.  Then the invalid
  *   codes are detected while decoding.
  */
+#ifndef CONFIG_ONLY_BLOCK_2
 local int fixed(struct state *s)
 {
     static int virgin = 1;
@@ -573,6 +583,7 @@ local int fixed(struct state *s)
     /* decode data until end-of-block code */
     return codes(s, &lencode, &distcode);
 }
+#endif

 /*
  * Process a dynamic codes block.
@@ -668,7 +679,9 @@ local int dynamic(struct state *s)
     int err;                            /* construct() return value */
     short lengths[MAXCODES];            /* descriptor code lengths */
     short lencnt[MAXBITS+1], lensym[MAXLCODES];         /* lencode memory */
+#ifndef CONFIG_ONLY_BLOCK_2
     short distcnt[MAXBITS+1], distsym[MAXDCODES];       /* distcode memory */
+#endif
     struct huffman lencode, distcode;   /* length and distance codes */
     static const short order[19] =      /* permutation of code length codes */
         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
@@ -676,8 +689,10 @@ local int dynamic(struct state *s)
     /* construct lencode and distcode */
     lencode.count = lencnt;
     lencode.symbol = lensym;
+#ifndef CONFIG_ONLY_BLOCK_2
     distcode.count = distcnt;
     distcode.symbol = distsym;
+#endif

     /* get number of lengths in each table, check lengths */
     nlen = bits(s, 5) + 257;
@@ -735,9 +750,11 @@ local int dynamic(struct state *s)
         return -7;      /* incomplete code ok only for single length 1 code */

     /* build huffman table for distance codes */
+#ifndef CONFIG_ONLY_BLOCK_2
     err = construct(&distcode, lengths + nlen, ndist);
     if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1]))
         return -8;      /* incomplete code ok only for single length 1 code */
+#endif

     /* decode data until end-of-block code */
     return codes(s, &lencode, &distcode);
@@ -816,6 +833,7 @@ int puff(unsigned char *dest,
         do {
             last = bits(&s, 1);         /* one if last block */
             type = bits(&s, 2);         /* block type 0..3 */
+#ifndef CONFIG_ONLY_BLOCK_2
             err = type == 0 ?
                     stored(&s) :
                     (type == 1 ?
@@ -823,6 +841,10 @@ int puff(unsigned char *dest,
                         (type == 2 ?
                             dynamic(&s) :
                             -1));       /* type == 3, invalid */
+#else
+           /* only support block type 2 */
+            err = type == 2 ? dynamic(&s) : -1;
+#endif
             if (err != 0)
                 break;                  /* return with error */
         } while (!last);