tjm-ext.nw

% -*- mode: Noweb; noweb-code-mode: c-mode; -*-
% Build with noweb:
%  notangle -t8 build.nw > makefile
%  make
\documentclass[twoside,english]{article}
\usepackage[letterpaper,rmargin=1.5in,bmargin=1in]{geometry}
%%% latex preamble
\RCS $Id$
\RCS $Revision$
\RCS $Date$

%%% requires build

\begin{document}

\title{Miscellaneous Programming Support for Literate Programs}
\author{Thomas J. Moore}
\date{Version \RCSRevision\\\RCSDate}
\maketitle

\begin{abstract}
Since I am pretty set in my ways, I may as well write some of them
down so that I don't have to repeat myself with every project.  This
document describes and implements a number of simple support blobs for
my literate programs.

This document, and its contents, are in the public domain.  While some
pieces may appear to be copied from other freely licensed documents I
have written, no pieces included here were not developed independently
before copying them into those documents, making them the actual copies.

This document was generated from the following sources, all of which
are attached to the original electronic forms of this document:

\input{Sources.tex} % txt
\end{abstract}

\tableofcontents

\lstset{language=sed}
<<Common noweb Warning>>=
# $Id$
@

\lstset{language=txt}
<<Sources>>=
$Id$
@

\lstset{language=C}
<<Version Strings>>=
"$Id$\n"
@

\section{Memory}

I do a lot of simple memory allocations, and it's easy to forget to
include the sizeof(element) scale factor.  To make this easier, here
are a few macros.  My usual behavior with memory allocation failures
is to print a message and exit the entire program, but I also provide
macros that can do something different, instead.

<<mallocdef.h>>=
<<Common C Warning>>
#ifndef MALLOCDEF_H
#define MALLOCDEF_H

<<Convenience definitions for dealing with memory>>
#endif /* MALLOCDEF_H */
@

<<Convenience definitions for dealing with memory>>=
#define err_buf(buf) do { \
   perror("Allocating memory for " #buf); \
   exit(1); \
} while(0)
#define resize_err(buf, len, err) do { \
    buf = realloc(buf, (len) * sizeof(*(buf))); \
    if(!(buf)) { \
        err; \
    } \
} while(0)
#define inisize_err(buf, len, err) do { \
    buf = malloc((len) * sizeof(*(buf))); \
    if(!(buf)) { \
        err; \
    } \
} while(0)
#define resize(buf, len) resize_err(buf, len, err_buf(buf))
#define inisize(buf, len) inisize_err(buf, len, err_buf(buf))
#define clearbuf(buf, len) memset(buf, 0, (len) * sizeof(*(buf)))
#define movebuf(dst, src, len) memmove(dst, src, (len) * sizeof(*(dst)))
#define cpybuf(dst, src, len) memcpy(dst, src, (len) * sizeof(*(dst)))
#define cmpbuf(a, b, len) memcmp(a, b, (len) * sizeof(*(a)))
@

<<Common C Includes>>=
#include "mallocdef.h"
@

In fact, the most common use of [[resize]] is to resize a buffer if
the new length would exceed a maximum, while increasing the maximum at
the same time.  My old Ada version of simple resizable arrays had
three parameters: a start size, a maximum doubling size, and a maximum
size.  I do not support the maximum size in the macros below.  The
maximum doubling size is a size up to which the size should be doubled
when more space is needed.  To grow larger than the maximum doubling
size, the maximum doubling size is added to the size, instead.  This
way, the array grows quickly when needed without wasting massive
amounts of space when large.  Rather than provide macros which do all
of this, here is a macro which chooses arbitrary constants for this.
Note that it is not possible to resize parallel arrays at the same
time with this macro.  To do that, the original size would need to be
saved, and the others resized if a change occurred.

<<Convenience definitions for dealing with memory>>=
/* arbitrary lower limit */
#ifndef MIN_MALLOC_SIZE
#define MIN_MALLOC_SIZE 16
#endif
/* when to stop doubling; set to ~0ULL to never stop */
#ifndef MAX_MALLOC_DOUBLE
#define MAX_MALLOC_DOUBLE 128*1024*1024
#endif
/* max_len may be evaluated more than once */
/* buf and max_len should be lvals */
#define check_size_err(buf, max_len, new_len, err) do { \
  size_t _new_len = new_len; \
  size_t _cur_max = max_len; \
  if(_new_len <= _cur_max) \
    break; \
  if(!(max_len)) { \
    if(_new_len < MIN_MALLOC_SIZE) \
      _new_len = MIN_MALLOC_SIZE; \
    inisize_err(buf, max_len = _new_len, err); \
  } else if(_new_len < MAX_MALLOC_DOUBLE) { \
    while(_new_len > _cur_max) \
      _cur_max *= 2; \
    resize_err(buf, max_len = _cur_max, err); \
  } else { \
    _new_len = (_new_len + MAX_MALLOC_DOUBLE - 1) / MAX_MALLOC_DOUBLE; \
    if(_new_len * MAX_MALLOC_DOUBLE <= _cur_max) { \
      /* errno = ENOSPC; */ \
      err; \
    } \
    resize(buf, max_len = _new_len * MAX_MALLOC_DOUBLE); \
  } \
} while(0)
#define check_size(buf, max_len, new_len) \
  check_size_err(buf, max_len, new_len, err_buf(buf))
@

While the above is useful for arrays which may shrink as well expand,
arrays that only expand only really need to track their length.

<<Convenience definitions for dealing with memory>>=
/* len may be evaluated more than once */
/* buf and len should be lvals */
#define grow_size_err(buf, len, new_len, err) do { \
  size_t _new_len = new_len, _cur_len = len; \
  len = _new_len; \
  size_t _max_len = MIN_MALLOC_SIZE; \
  while(_max_len < _cur_len && _max_len < MAX_MALLOC_DOUBLE) \
    _max_len *= 2; \
  if(_max_len < _cur_len) \
    _max_len = (_cur_len + MAX_MALLOC_DOUBLE - 1) / MAX_MALLOC_DOUBLE; \
  if(_cur_len && _max_len >= _new_len) \
    break; \
  while(_max_len < _new_len && _max_len < MAX_MALLOC_DOUBLE) \
    _max_len *= 2; \
  if(_max_len < _new_len) \
    _max_len = (_new_len + MAX_MALLOC_DOUBLE - 1) / MAX_MALLOC_DOUBLE; \
  if(!_cur_len) \
    inisize_err(buf, _max_len, err); \
  else \
    resize_err(buf, _max_len, err); \
} while(0)
#define grow_size(buf, len, new_len) \
  grow_size_err(buf, len, new_len, err_buf(buf))
@

\section{Warnings}

I also prefer a little bit higher warning level than the default.  I
probably ought to provide a [[makefile.config.defaults]] as a separate
file, since the [[makefile]] only comes from [[build.nw]].

\lstset{language=make}
<<makefile.vars>>=
ifeq ($(CC),cc)
CC=gcc
endif
ifeq ($(CFLAGS),)
CFLAGS=-O2
endif
# -ftrack-macro-expansion would be useful with gcc-4.7.x (default on 4.8)
EXTRA_CFLAGS += -Wall -Wmissing-declarations -Wno-unused-result -Wshadow \
                -Wmissing-prototypes
EXTRA_CXXFLAGS += -Wall -Wmissing-declarations -Wno-unused-result -Wshadow
@

\section{Types}

These days, I try to use the standard C types that have specific sizes.

\lstset{language=C}
<<Common C Includes>>=
#include <stdint.h>
@

<<Known Data Types>>=
% stdint.h
int8_t,uint8_t,int16_t,uint16_t,int32_t,uint32_t,int64_t,uint64_t,%
@

\section{GLib}

I use GLib a lot in recent C projects, to avoid having to reimplement
some common dynamic data structures (even though I'm not entirely
happy with how GLib implements things).

\lstset{language=make}
<<makefile.vars>>=
ifneq ($(USES_GLIB),)
GLIB_CFLAGS:=$(shell pkg-config --silence-errors gthread-2.0 --cflags || \
                     pkg-config glib-2.0 "--cflags")
GLIB_LDFLAGS:=$(shell pkg-config --silence-errors gthread-2.0 --libs || \
                      pkg-config glib-2.0 --libs)
EXTRA_CFLAGS += $(GLIB_CFLAGS) -DUSES_GLIB
EXTRA_LDFLAGS += $(GLIB_LDFLAGS)
else
# don't offer USES_GLIB if it's not supported in binary
NOTANGLE_POSTPROC+=|sed -e 's/ifdef USES_GLIB/if 0/'
endif
@

\lstset{language=C}
<<Common C Includes>>=
#ifdef USES_GLIB
#include <glib.h>
#endif
@

<<Known Data Types>>=
% GLib
gboolean,gint8,guint8,gint16,guint16,gint32,guint32,gint64,guint64,%
gchar,guchar,gint,guint,glong,gulong,GString,GStringChunk,GArray,GByteArray,%
GPtrArray,gconstpointer,gpointer,GMemChunk,GDir,GError,%
@

One thing that is missing that I have always found useful is a version
of [[fgets]](3) which supports dynamic strings.  Such a function is
easy enough to implement, so here it is, both a GLib version which
returns a [[GString]], and a simpler version that just returns an
allocated buffer.  A generic version is provided as well for cases
where [[fgets]]-equivalent functions are available.

When reading binary data that may contain NUL characters, the buffer length
must be updated based not on [[strlen]], but on the number of characters
read.  This can be obtained from [[ftell]] only for seekable streams, so the
only option with [[fgets]] is to fill the memory with non-NUL characters and
search for the last added NUL.  Another option would be to use a different
reader function.  The CPU overhead for using [[getc]] for every character is
pretty high, though, and [[fscanf]] has issues with NUL characters as well.
Implementing a wrapper around [[fread]] would require that all reads from
the file be done using this function in order to take care of backlog.

In order to avoid the processing overhead for NULs for most reads, the
wrapper has two names, and the generic function takes a parameter to enable
this.

<<Library [[tjm-supt]] Members>>=
g_string_fgets.o
mfgets.o
@

<<mfgets.h>>=
/*
  <<Common noweb Warning>>
*/
#ifndef _MFGETS_H
#define _MFGETS_H

#include <stdio.h>

<<[[mfgets]] prototypes>>

#endif /* _MFGETS_H */
@

<<Common C Includes>>=
#include "mfgets.h"
@

<<[[mfgets]] prototypes>>=
typedef char *(*gets_fp)(char *buf, int len, void *f);
@

<<Known Data Types>>=
gets_fp,%
@

<<[[mfgets]] prototypes>>=
#ifdef USES_GLIB
char *g_string_fgets(GString **_buf, guint offset, FILE *f);
char *g_string_fgets_bin(GString **_buf, guint offset, FILE *f);
char *g_string_fgets_generic(GString **_buf, guint offset, gets_fp my_gets,
                             void *f, gboolean allow_zero);
#endif
@

<<g_string_fgets.c>>=
<<Common C Header>>

#ifdef USES_GLIB
char *g_string_fgets(GString **_buf, guint offset, FILE *f)
{
  return g_string_gets_generic(_buf, offset, (gets_fp)fgets, f, FALSE);
}

char *g_string_fgets_bin(GString **_buf, guint offset, FILE *f)
{
  return g_string_gets_generic(_buf, offset, (gets_fp)fgets, f, TRUE);
}

char *g_string_gets_generic(GString **_buf, guint offset, gets_fp my_gets,
                            void *f, gboolean allow_zero)
{
  guint left, len;
  GString *buf = *_buf;
  gboolean read_some = FALSE;
  const char *ep;

  if(!buf)
    buf = *_buf = g_string_sized_new(offset + 80);
  else if(buf->allocated_len <= offset + 1)
    g_string_set_size(buf, offset + 80);
  while(1) {
    left = buf->allocated_len - offset;
    if(allow_zero)
      memset(buf->str + offset, 255, left);
    else /* still need to detect end of line */
      buf->str[offset + left - 1] = 255;
    if(!(*my_gets)(buf->str + offset, left, f)) {
      buf->str[offset] = 0;
      break;
    }
    read_some = TRUE;
    if(allow_zero) {
      /* memrchr is GNU extension, so this is done manually */
      /* guaranteed to terminate */
      for(ep = buf->str + buf->allocated_len - 1; *ep; ep--);
      len = (int)(ep - buf->str) - offset;
    } else
      len = strlen(buf->str + offset);
    left -= len;
    offset += len;
    if((left > 1 && buf->str[offset + left - 1]) ||
       buf->str[offset - 1] == '\n')
      break;
    g_string_set_size(buf, buf->allocated_len * 2 - 1);
  }
  buf->len = offset;
  return read_some ? buf->str : NULL;
}
#endif
@

<<[[mfgets]] prototypes>>=
char *mfgets(char **buf, unsigned int *buflen, unsigned int *retlen,
             unsigned int offset, FILE *f);
char *mfgets_bin(char **buf, unsigned int *buflen, unsigned int *retlen,
                 unsigned int offset, FILE *f);
char *mfgets_generic(char **buf, unsigned int *buflen,
		     unsigned int *retlen, unsigned int offset,
		     gets_fp my_gets, void *f, int allow_zero);
@

<<mfgets.c>>=
<<Common C Header>>

char *mfgets(char **buf, unsigned int *buflen, unsigned int *retlen,
             unsigned int offset, FILE *f)
{
  return mfgets_generic(buf, buflen, retlen, offset, (gets_fp)fgets, f, 0);
}

char *mfgets_bin(char **buf, unsigned int *buflen, unsigned int *retlen,
                 unsigned int offset, FILE *f)
{
  return mfgets_generic(buf, buflen, retlen, offset, (gets_fp)fgets, f, 1);
}

char *mfgets_generic(char **buf, unsigned int *_buflen,
		     unsigned int *retlen, unsigned int offset,
		     gets_fp my_gets, void *f, int allow_zero)
{
  int left, len;
  int read_some = 0;
  int buflen = _buflen ? *_buflen : buf ? strlen(*buf) : 0;
  const char *ep;

  if(!*buf) {
    buflen = offset + 80;
    inisize(*buf, buflen);
  } else if(buflen <= offset + 1) {
    buflen = offset + 80;
    resize(*buf, buflen);
  }
  while(1) {
    left = buflen - offset;
    if(allow_zero)
      memset(*buf + offset, 255, left);
    else /* still need to detect end of line */
      (*buf)[offset + left - 1] = 255;
    if(!(*my_gets)(*buf + offset, left, f)) {
      (*buf)[offset] = 0;
      break;
    }
    read_some = 1;
    if(allow_zero) {
      /* memrchr is GNU extension, so this is done manually */
      /* guaranteed to terminate */
      for(ep = *buf + buflen - 1; *ep; ep--);
      len = (int)(ep - *buf) - offset;
    } else
      len = strlen(*buf + offset);
    left -= len;
    offset += len;
    if((left > 1 && (*buf)[offset + left - 1]) ||
       (*buf)[offset - 1] == '\n')
      break;
    buflen *= 2;
    resize(*buf, buflen);
  }
  if(_buflen)
    *_buflen = buflen;
  if(retlen)
    *retlen = offset;
  return read_some ? *buf : NULL;
}
@

Similarly, a version of [[getcwd]] that never overflows and does not
require a static maximum path length is useful.  GLib already provides
such a function ([[g_get_current_directory]]), so this is only needed
for non-GLib use.  Actually, GNU libc also provides several such
functions, but their existence cannot be relied on.  It doesn't hurt to
combine this with the routines above into the same header and library.

<<[[mfgets]] prototypes>>=
#ifdef __GLIBC__
#include <unistd.h>
#define getcwd_full() getcwd(NULL, 0)
#else
char *getcwd_full(void);
#endif
@

<<mfgets.c>>=
#ifndef __GLIBC__
#include <errno.h>
char *getcwd_full(void)
{
  unsigned int maxlen = 20;
  char *buf = malloc(maxlen), *ret;
  if(!buf)
    return NULL;
  while(1) {
    ret = getcwd(buf, maxlen);
    if(ret)
      return ret;
    if(errno != ERANGE) {
      int eno = errno;
      free(buf);
      errno = eno;
      return NULL;
    }
    maxlen *= 2;
    ret = realloc(buf, maxlen);
    if(!ret) {
      free(buf);
      return NULL;
    }
    buf = ret;
  }
}
#endif
@

\section{Binary Tricks}

% l2h substitution lceil &lceil;
% l2h substitution rceil &rceil;

The following is code to count the number of set bits, find the
minimum mask including the last set bit (since there is no [[fls]]
function to complement [[ffs]](3)) and to use the above two to find
$\lceil \log_2 x \rceil$.  While I normally don't like defining code
in headers, doing so ensures inlining of code with sufficient
optimization.

<<Common C Includes>>=
#include "btricks.h"
@

<<btricks.h>>=
<<Common C Warning>>
#ifndef BTRICKS_H
#define BTRICKS_H

#include <stdint.h>

#ifdef __GNUC__
#define _unused_attr __attribute__((__unused__))
#else
#define _unused_attr
#endif

static uint32_t _unused_attr count_bits(uint32_t l)
{
  l = ((l & 0xaaaaaaaa) >> 1) + (l & 0x55555555);
  l = ((l & 0xcccccccc) >> 2) + (l & 0x33333333);
  l = ((l & 0xf0f0f0f0) >> 4) + (l & 0x0f0f0f0f);
  l = ((l & 0xff00ff00) >> 8) + (l & 0x00ff00ff);
  l = ((l & 0xffff0000) >> 16) + (l & 0x0000ffff);
  return l;
}

static uint32_t _unused_attr count_bits64(uint64_t l)
{
  l = ((l & 0xaaaaaaaaaaaaaaaaULL) >> 1) + (l & 0x5555555555555555ULL);
  l = ((l & 0xccccccccccccccccULL) >> 2) + (l & 0x3333333333333333ULL);
  l = ((l & 0xf0f0f0f0f0f0f0f0ULL) >> 4) + (l & 0x0f0f0f0f0f0f0f0fULL);
  l = ((l & 0xff00ff00ff00ff00ULL) >> 8) + (l & 0x00ff00ff00ff00ffULL);
  l = ((l & 0xffff0000ffff0000ULL) >> 16) + (l & 0x0000ffff0000ffffULL);
  l = ((l & 0xffffffff00000000ULL) >> 32) + (l & 0x00000000ffffffffULL);
  return l;
}

/* set all bits below last set bit */
static uint32_t _unused_attr min_mask(uint32_t l)
{
  l |= l >> 1;
  l |= l >> 2;
  l |= l >> 4;
  l |= l >> 8;
  l |= l >> 16;
  return l;
}

/* set all bits below last set bit */
static uint64_t _unused_attr min_mask64(uint64_t l)
{
  l |= l >> 1;
  l |= l >> 2;
  l |= l >> 4;
  l |= l >> 8;
  l |= l >> 16;
  l |= l >> 32;
  return l;
}

#define fls(x) count_bits(min_mask(x)) /* same interpretation as ffs */
#define fls64(x) count_bits64(min_mask64(x))
/* lg2(x) is undefined at 0, but actually will return max value */
#define lg2(x) fls((x) - 1)
#define lg264(x) fls64((x) - 1)

#endif /* BTRICKS_H */
@

\section{Timing}

Some design decisions require timing tests.  To support this, here are
some simple routines to include into a file for time testing.  This is
not provided as either an include file or binary library:  you must
explicitly include the code chunk [[<<POSIX timing support>>]].

Microsecond timings are easy to get and standard, but for fast CPUs,
it may be difficult to make a process last long enough for timings to
be valid (i.e., for less than 5% variability, it would need to last at
least 20 microseconds).  I know of no portable way to get nanosecond
timings, so I'll only provide these for Linux with GNU libc.
Technicially, this method is only valid with Linux 2.6.12+ and
sufficiently recent GNU libc, but it's not likely that such old
kernels or critical system libraries are used much any more.

<<POSIX timing support>>=
#if defined(__linux__) && defined(__GLIBC__)
#include <time.h>
static struct timespec time0;

static void tstart(void)
{
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time0);
}

static double tend(void)
{
  struct timespec time1;
  clock_gettime(CLOCK_THREAD_CPUTIME_ID, &time1);
  double ret = (double)(time1.tv_sec - time0.tv_sec) * 1000000.0;
  return ret + (double)(time1.tv_nsec - time0.tv_nsec) / 1000.0;
}
#else
#include <sys/resource.h>
static struct rusage time0;

static void tstart(void)
{
  getrusage(RUSAGE_SELF, &time0);
}

static double tend(void)
{
  struct rusage time1;
  getrusage(RUSAGE_SELF, &time1);
  double ret = (double)(time1.ru_utime.tv_sec - time0.ru_utime.tv_sec) * 1000000.0;
  return ret + (double)(time1.ru_utime.tv_usec - time0.ru_utime.tv_usec);
}
#endif
@

\section{Variable-Length Values in Byte Arrays}

This is mostly lifted from my pattern matcher (and is now used in it).
The idea is simple:  bytes are commonly the most efficient way to
store stuff.  However, bytes can't store values larger than 255.  To
fix this, values can be encoded with continuation bits.  I support 3
data types in byte arrays:  8-bit values (always stored raw), unsigned
variable-length integers, and signed variable-length integers.  Signed
variable-length integers are stored by shifting their absolute value
left by one, and setting bit zero to the sign.

Like the previous section, this is only available as a noweb macro.
You must specify the size (usually 32 or 64) when expanding this.

<<Support for Byte Array With Variable-Length (@sz)-bit Values>>=
/* split is > 0 for positive split, < 0 for negative split */
/* 0 = no split */
static int ba_val_len(uint<<@sz>>_t val, int split)
{
  int vlen;
  if(!split)
    return 1;
  else if(split > 0) {
    uint<<@sz>>_t t;
    for(t = val, vlen = 1; t > 0x7f; t >>= 7, vlen++);
  } else {
    int<<@sz>>_t sv = (int<<@sz>>_t)val;
    uint<<@sz>>_t t = (uint<<@sz>>_t)(sv < 0 ? -sv : sv);
    if(t <= 0x3f)
      vlen = 1;
    else {
      t >>= 6;
      for(vlen = 2; t > 0x7f; t >>= 7, vlen++);
    }      
  }
  return vlen;
}
@

<<Support for Byte Array With Variable-Length (@sz)-bit Values>>=
#define ba_set_val(set_loc, loc0, split, val) do { \
  uint<<@sz>>_t _t = val; \
  unsigned long _loc = loc0; \
  if(!split) { \
    set_loc(_loc, _t); \
  } else { \
    uint8_t _vb; \
    if(split < 0) { \
      _vb = (int<<@sz>>_t)_t < 0; \
      if(_vb) \
        _t = -(uint<<@sz>>_t)_t; \
      _vb |= (_t & 0x3f) << 1; \
    } else { \
      _vb = _t & 0x7f; \
      _t >>= 7; \
    } \
    while(1) { \
      if(_t) \
        _vb |= 0x80; \
      set_loc(_loc, _vb); \
      if(!_t) \
        break; \
      _vb = _t & 0x7f; \
      _t >>= 7; \
      ++_loc; \
   } \
  } \
} while(0)
@

<<Support for Byte Array With Variable-Length (@sz)-bit Values>>=
/* returns the value in val and its length in len; both must be lvals */
#define ba_get_val(val, len, get_loc, loc0, split) do { \
  unsigned long _loc = loc0; \
  if(!split) { \
    len = 1; \
    val = get_loc(_loc); \
    break; \
  } \
  uint<<@sz>>_t _ret = 0, _atloc = get_loc(_loc); \
  unsigned int _shift, _rlen = 1; \
  int _do_neg = 0; \
  if(split < 0) { \
    _do_neg = _atloc & 1; \
    _ret = (_atloc >> 1) & 0x3f; \
    _shift = 6; \
  } else { \
    _ret = _atloc & 0x7f; \
    _shift = 7; \
  } \
  while(_atloc & 0x80) { \
    _atloc = get_loc(_loc); \
    _ret |= (_atloc & 0x7f) << _shift; \
    ++_loc; \
    ++_rlen; \
    _shift += 7; \
  } \
  len = _rlen; \
  if(_do_neg) \
    _ret = (uint<<@sz>>_t)-(int<<@sz>>_t)_ret; \
  val = _ret; \
} while(0)
@

\section{Code Index}
\nowebchunks

\end{document}