BLT

From Ft Wm, Inv & Tor CC

BLT is a text-based file format used to record (voting) 'preference profiles' in STV elections. Highland Council's election software uses it and HRC election results are made publicly available in it. In December 2021, EMD wrote a C program to read a BLT file and determine the winner of a single-seat (aka AV) election, given below (to copy it: select Read/Edit source, above). Other than that the 'T' seems likely to stand for 'table', the meaning of the acronym 'BLT' is not known.

NB: Originally, some of the asterisks were displaying as bullet-points below; this and other artifacting was due to the way MediaWiki processes free text. The workaround was to indent the whole damnéd thing by a couple of spaces: I'll try to fix it properly at some point. -S Ftwm (talk) 11:18, 17 December 2021 (GMT)

 /** This program is (C) E M Drayton 2021.  Modification is prohibited.
 *** You are free to compile and run it for non-commercial purposes.
 **/
 
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
 #include <errno.h>
 
 /**
 #include <math.h>
 **/
 
 #include <assert.h>
 static void (die)(const int line);
 #define die() die(__LINE__);
 
 #define C 20
 #define C_ 32
 #define H_(X) (#X)
 #define H(X) H_(X)
 
  /*\ \*/ /*\ \*/ /*\ \*/
 
 static long lines(const char *const t_, FILE *const e) {
   const char *t= t_, *u;
   long l= 0;
 
   for (; (u= strchr(t, '\n')) != 0; t= u+1) ++l;
 
   !e || fprintf(e, "  %ld lines in %ld octets\n", l, (long)strlen(t_));
 
   return l;
 }
 
  /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/
 
 struct rec; typedef struct rec rec; struct rec {
   unsigned char *p;
   int c;
   long d;
   short *v;
   unsigned char **w;
   short a[1][C_][C_];
 };
 
 #define p_ (r->p)
 #define c_ (r->c)
 #define d_ (r->d)
 #define v_ (r->v)
 #define w_ (r->w)
 #define a_ (r->a)
 
  /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/
 
 static void eliminate(const rec *const r, const int c) {
   unsigned char **p= w_, *q;
   const int k= tolower(c);
   long l= d_+1;
 
   while (--l) if ((q= *++p) == 0 || (q= strchr(q, c)) == 0); else *q= k;
 }
 
  /*\ \*/ /*\ \*/ /*\ \*/
 
 static unsigned long losers_(const short (*p)[C_], const int c, unsigned long v) {
   unsigned long u= (1ul<<c)-1, t;
   unsigned n= 0u-1;
   int i= C_-c;
 
   ++p;
   while (u) {
     u>>= 1; t= u+1;
     if (!(v&t)) ++i; else {
       unsigned f= (*p)[-++i];
 
       if (f>n) v^= t; else if (f<n) { v&= t|u; n= f; } else;
     }
   }
   assert(i==C_); /* fprintf(stderr, " %0*loo", (c+2)/3+1, v); /**/
 
   return v;
 }
 
 static unsigned long losers(const rec *const r, unsigned long v) {
   const short (*p)[C_]= a_[1];
   unsigned long w= v;
 
   while (w && p > *a_) {
     v= w; w= losers_(--p, c_, v);
   }
 
   return v;
 }
 
  /*\ \*/ /*\ \*/ /*\ \*/
 
 static void count(rec *const r, FILE *e) {
   long l;
 
   memset(a_, 0, sizeof *a_);
 
   for (l= d_+1; --l;) {
     short (*f)[C_]= a_[1];
     unsigned h= v_[l];
     const unsigned char *s= w_[l];
     int c;
 
     assert(h); /* fprintf(stderr, "  %u: '%s' ", h, s); /**/
 
     while ((c= *++s)!=0) if (!isupper(c)); else (*--f)[c-'A']+= h;
   }
 /* putc('\n', stderr); /**/
 
   if (!e); else { int i, j; const int c= c_;
 
     !e || fputs("PREFS:-\n", e);
     for (j= -1+C_-c; ++j < C_; !e || putc('\n', e))
     for (i= -1; ++i < c; !e || putc(',', e))
     if (!(*a_)[j][i]); else { static char a[9];
       sprintf(a, "%d", (*a_)[j][i]);
       !e || fprintf(e, "%5s", a);
     }
     !e || fputs("END (OK)\n\n", e);
   }
 }
 #define recount count
 
  /*\ \*/ /*\ \*/ /*\ \*/
 
 #undef NDEBUG
 /** Using assert() to report runtime errors is, admittedly, very fckg lazy. -EMD
 **/
 #include <assert.h>
 
 static void (die)(int line) {
 
   if (line); else {
     fprintf(stderr, "\n\nThe C program '%s' reads generic STV files but it only knows how to work out who won AV (ie single-seat) elections with a maximum of %s candidates, unfortunately.  Try asking EMD for an upgraded version.\n", __FILE__, C==20? "twenty": H(C)); fflush(0);
     assert(!"I'm too stupid to work this out, sorry.");
 }
 
   fprintf(stderr, "\n\nYour crappy wee computer doesn't have enough memory to run the C program '%s', which is why it gave up trying somewhere around line %d.\n", __FILE__, line); fflush(0);
   assert(!"I'm shit out of memory, sorry.");
 }
 
  /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/ /*\ \*/
 
 /** 
 *** fscanf() first line and validate it completely
 ***   (basically a sanity check for the file)
 *** fseek to the end and measure it
 ***   (sanity check the length???)
 *** allocate and load
 *** count the lines
 *** allocate an Iliffe (or not?)
 ***   (no more allocs now!)
 *** find the first non-digit/SP/CR/LF
 *** count the lines from there and validate totals
 **/
 
 #ifdef E
 #else
 #define E stdout
 #endif
 #define E_ (!(E))
 
 extern int main(int ac, const char *const *av) {
   static rec r[1];
   const char *s= av[ac-1];
   FILE *f;
   int c, e;
   long d, l;
   size_t z;
   unsigned char *p;
 
 for(e= 50; --e;) fputc('\n', stderr); /**/
 
   errno= 0;
   assert(ac >= 2);
   f= fopen(s, "rb");
   if (f); else { perror(s); return 0; }
   assert(f && !ferror(f));
 
   { static int a[3]= { 0 }; int b;
 
     fscanf(f, "%2d%*1[ ]%d%*1[\r]%*1[\n]%n", a+1, a+2, a);
 
     c= a[1]; b= a[2]; e= *a; assert(e);
     if (c<=C && c>=1 && b==1); else (die)(0);
     assert(c<=C && c>=1 && b==1);
   }
 
   fseek(f, 0, SEEK_END); assert(!ferror(f));
   z= ftell(f); assert(!ferror(f));
 
 #define V 2
   p= malloc(z+V); if (p); else die(); assert(p);
   p+= V-(V>>1); p[-1]= '0'; p[z]= 0;
   E_ || fprintf(E, "\nAllocated %ld octets OK\n", (long)z+V);
 #undef V
 
   rewind(f); assert(!ferror(f));
 
 #define P ((const char *)(void *)p)
 
   { static const char k[]= " 0\r\n0\r\n";
     size_t r= fread(p, z, 1, f);
 
     if (!errno); else { perror(s); fflush(0); }
     assert(!ferror(f)); assert(!feof(f)); assert(!errno); assert(r);
 
     r= fgetc(f)-EOF; assert(!ferror(f)); assert(feof(f)); assert(!r);
     fclose(f); assert(!errno);
     assert(!p[z]); assert(p[z-1]=='\n'); r= strlen(P); assert(r==z);
 
 #define K ((sizeof k) - 1)
     r= strspn(P, "01234567890 \r\n"); assert(isupper(p[r+(p[r]=='\"')]));
     assert(r>K && !strncmp(P+(r-K), k, K));
 #undef K
 
     d= lines(p+r, E); assert(d==c+1l);
     l= lines(p, E)-d; d= l-2l; l+= c+3l;
   }
 
 /* assert(c==7); assert(d==516); assert(l==528); assert(e==5); /**/
 
   { short *v; unsigned char **w; ptrdiff_t y= sizeof(void *)+sizeof(short);
 
     w= calloc(l, y); if (w); else die(); assert(w);
     v= (short *)(void *)(w+l);
     p+= e; assert(p[-1]=='\n');
     p_= p; c_= c; d_= d; v_= v; w_= w;
     E_ || fprintf(E, "\nAllocated %ld octets OK\n", l*y);
   }
 
   if (!errno); else { perror(s); fflush(0); }
   assert(!errno);
 
  /*\ \*/ /*\ \*/ /*\ \*/
 
   E_ || fprintf(E, "\nProcessing %ld octets from file '%s'\n", (long)z, s);
 
   { static int n[2]= { 0, 0 };
     int *q= n; const char *t= P; char *u; unsigned phase= 2u;
     char **p= (char **)(void *)w_;
     short *v= v_;
 
     *p= 0; *v= 0;
 
     for (; (u= strchr(t, '\n')) != 0; t= u+1) {
       assert(u[-1]=='\r');
       assert(u[-2]=='0' || phase==1u && u[-2]=='\"');
       if (u-t >= 3) ++*q;
       else { phase>>= 1; assert(phase); assert(*q==d); ++q; }
       assert(u[-3]==' ' || phase==1u && (u[-2]==(u-t >= 3? '\"': '0')));
       assert(isdigit(u[-4]) || phase==1u);
 
       *u= 0; u[-1]= 0;
       if (phase==1u) {
           if (u[1]=='\"'); else { assert(!u[1]); assert(*q==c+1l); }
       } else { assert(isdigit(u[1]));
 
 #if 0
 u[-2]= 0; /* u[-3]= 0; /**/ }
 #else
           { char *const cp= (char *)((long)u-3ul|1ul);
             unsigned short *const hp= (unsigned short *)(cp+1);
 
             *u= '0'; *cp= 0; *hp= 257;
             /* TODO= assert something about all this (or get rid of it?) */
           }}
 #endif
 
       l= strtol(t, ++p, 10); assert(l>0 || !l && phase==1u);
 assert(l<=1999); /* sanity; 11 bits (lose?) */
       *++v= (short)l; assert(*v==l);
 
       if (**p==' '); else { assert(!l); continue; }
 
       { static char *e[1], a[101];
         int k= *++*p;
         char *q= a;
 
         assert(isdigit(k) && k!='0');
         *q= ' '; *e= *p;
 
         do {
             l= strtol(*e, e, 10);
             if (l>0) {
                 assert(l<=C);
                 *++q= 'A'+c-(int)l;
             } else assert(!l);
         } while (l);
 
         *++q= 0; l= strlen(*p);
         sprintf(*p, "%*s", (int)l, a); *p+= l-(q-a);
       }
     }
     E_ || fprintf(E, "\n%ld profiles, %ld strings\n", (long)n[0], (long)n[1]);
   }
 #undef P
 
  /*\ \*/ /*\ \*/ /*\ \*/
 
   { unsigned long v= (1ul<<c)-1ul, w= 0; int k; unsigned once= 2u;
     unsigned char *const *const s_= w_+d_+c_+1;
 
     puts("\n--\n\nRESULTS:\n"); /**/
 
     do {
         for (k= 'A'; w>>= 1; ++k)
           if (~(unsigned)w&1u);
           else {
             printf("  #%d('%c') lost ('%s')\n", 'A'+c_-k, k, s_['A'-k]);
             eliminate(r, k);
           }
         if (!(once>>= 1)) recount(r, 0); else count(r, E);
         w= losers(r, v); v^= w; w<<= 1;
     } while (v);
 
     printf("\nResult (%0*loo) in '%s':\n\n", (c+2)/3+1, w>>1, s_[1]); /**/
 
     for (k= 'A'; w>>= 1; ++k)
       if (~(unsigned)w&1u);
       else { printf("  #%d('%c') won ('%s')\n", 'A'+c_-k, k, s_['A'-k]); }
   }
 
   return EXIT_SUCCESS;
 }
 
 #undef E
 #undef C
 #undef C_
 #undef H
 #undef H_