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.

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?

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);

Can I use this embedded processor?

At work I'm asked if we can use a particular processor for a new system. Other than mechanical, electrical, and I/O considerations, software and tool support is very important.

When selecting processors for medium-sized embedded systems, I ask:

Is it a well-known architecture? For our applications, we stick with ARM, MIPS. We evaluated Intel, but they didn't meet our I/O requirements.

Linux support? I check Wikipedia and the Linux repository.

GCC support? I check the GCC repository.

ICE/JTAG support? I check Mentor Graphics and Macraigor.

Shell programming: pipefail

Today I discovered Bash's pipefail option. For a relevant blog post, see this.

So now all of my Bash scripts will begin with "set -e; set -o pipefail;"

ViewVC error parsing rlog output

When trying to list a directory in ViewVC 1.1.13, I was getting the error:

An Exception Has Occurred

Python Traceback

Traceback (most recent call last):
File "/usr/share/viewvc/lib/viewvc.py", line 4537, in main
request.run_viewvc()
File "/usr/share/viewvc/lib/viewvc.py", line 394, in run_viewvc
self.view_func(self)
File "/usr/share/viewvc/lib/viewvc.py", line 2049, in view_directory
file_data, options)
File "/usr/share/viewvc/lib/vclib/ccvs/bincvs.py", line 261, in dirlogs
alltags = _get_logs(self, path_parts, entries_to_fetch, rev, subdirs)
File "/usr/share/viewvc/lib/vclib/ccvs/bincvs.py", line 1030, in _get_logs
raise vclib.Error('Error parsing rlog output. Expected RCS file %s'
Error: Error parsing rlog output. Expected RCS file /cvs/project/some/path/somefile.sh,v, found

After tracking this down, turns out that if the last line of your commit is:

=============================================================================

then you will get two back-to-back lines of all "=" in the rlog output, and ViewVC parsing will fail.

So, until this is fixed in ViewVC, you can edit the *,v files, and change the first character of the line from a "=" to something else.

Cross-compiling Perl for MIPS/ARM etc.

Here's me trying to cross-compile Perl for MIPS. I gave up eventually, but you may have better luck.

Instructions

1. Save patch file to my-compile-perl-001.patch
2. Save script to, say, my-compile-perl.sh
3. ./my-compile-perl.sh

When asked for Any additional cc flags? [none], enter -fno-strict-aliasing
When asked Do you wish to use dynamic loading? [y], enter n
Tweak a few more answers, but you can hit Enter and accept the
default for most. It still asks for remote root password
sometimes, not sure why.

GCC and unsigned enumerations

Enumerations in C are signed or unsigned in GCC depending on whether
one of the values is negative. This prohibits forward-looking checks
that expect that enumerations may include a negative value in the
future.

For example, say we had silly color_t enumeration:

typedef enum { RED = 0, GREEN = 1 } color_t;
const char * string_of_color (color_t color) {
    static const char * colors[2] = { "RED", "GREEN" };
    return colors[color];
}
int main(void) {
    printf("Color: %s\n", string_of_color(0));
}

The output will be:

Color: RED

The program may crash if main was to call string_of_color(10). So we'll put in a check:

typedef enum { RED = 0, GREEN = 1 } color_t;
const char * string_of_color (color_t color) {
    static const char * colors[2] = { "RED", "GREEN" };
    if (color < 0 || color > 1) return "INVALID";
    return colors[color];
}
int main(void) {
    printf("Color: %s\n", string_of_color(0));
}

But now GCC complains:

warning: comparison of unsigned expression < 0 is always false

This breaks things because I might expect that we'd change the color enumeration to:

typedef enum { INVALID = -1, RED = 0, GREEN = 1 } color_t;

Now my check is valid and GCC doesn't complain. My workaround?

if ((int)color < 0 || color > 1) return "INVALID";

Another possible workaround is to add a negative value in color_t or use a GCC compile-time option.

Data independent memcmp

My try at validating the memcmp function from this Tor diff using Frama-C. The loop_precondition is what I'm stuck on.

/*@ predicate IsValidRange( unsigned char *a, integer n ) =   @     ( 0 <= n ) && \valid_range( a, 0, n - 1 );
  @*/
/*@ requires \valid(x) && \valid(y);
  @ assigns nothing;
  @ 
  @ behavior zero_length:
  @  assumes len == 0;
  @  ensures \result == 0;
  @
  @ behavior equal:
  @  assumes len > 0;
  @  assumes x_y_equal : \forall integer n;
  @     0 <= n < len ==> x[n] == y[n];
  @  requires IsValidRange(x, len);
  @  requires IsValidRange(y, len);
  @  ensures \result == 0;
  @
  @ behavior not_equal:
  @  assumes len > 0;
  @  assumes x_y_not_equal : \exists integer n;
  @    0 <= n < len ==> x[n] != y[n];
  @  requires IsValidRange(x, len);
  @  requires IsValidRange(y, len);
  @  ensures \result != 0;
  @
  @ complete behaviors zero_length, equal, not_equal;
  @ disjoint behaviors zero_length, equal, not_equal;
  @*/
int
tor_memcmp(const unsigned char *x, const unsigned char *y, unsigned int len)
{
    unsigned int i = len;
    int retval = 0, newval;
    if (len == 0) return 0;
    while (i--) {
        //@ assert loop_precondition: (retval == 0) || (\exists integer n; i < n < len && x[i] != y[i]);
        int v1 = x[i];
        int v2 = y[i];
        int equal_p = v1 ^ v2;
        //@ assert (x[i] == y[i] && equal_p == 0) || (x[i] != y[i] && 0 < equal_p <= 255);
        // relies on two's complement!
        --equal_p;
        //@ assert (x[i] == y[i] && equal_p == -1) || (x[i] != y[i] && 0 <= equal_p < 255);
        // relies on signed right shift!
        equal_p >>= 8;
        //@ assert (x[i] == y[i] && equal_p == -1) || (x[i] != y[i] && equal_p =>= 0);
        newval = retval & equal_p;
        //@ assert (x[i] == y[i] && retval == newval) || (x[i] != y[i] && newval == 0);
        retval = newval;
        newval = retval + (v1 - v2);
        //@ assert (x[i] == y[i] && newval == retval) || (x[i] != y[i] && newval == (v1 - v2));
        retval = newval;
    }   
    return retval;
}

Types of random numbers

While reading these slides I came upon the following classification of random numbers:

• "Real" random numbers: use a physical source of randomness
• Pseudo-random numbers: deterministic sequence that passes tests of
  randomness
• Quasi-random numbers: well distributed (low discrepancy) points

I hadn't heard about quasi-random numbers before. Wikipedia links
to low-discrepancy sequence and has diagrams that point out the difference.

"Real" random numbers are often used in cryptographic applications, and
pseudo-random numbers are used all over the place in simulations and
games.

random.org has a good overview for the other two types:

Characteristic	Pseudo-random	Real-random
Efficiency	Excellent	Poor
Determinism	Deterministic	Non-deterministic
Periodicity	Periodic	Aperiodic