UNB/ CS/ David Bremner/ David Bremner's Blog
2D arrays C CGTA DAG ILP LP SAT absolute value aljazeera alleged-humour amarok ampl application argyll arrays asymptotics audio backtracking backup beamer bibutils binary file bipartite blogs blorg business caff censorship closure colorhug colour colour management column generation combinatorics cpan cplusplus cs3383 cs3383 lecture cs3613 cs4613 currying dantzig de Bruijn debian diet digikam divide and conquer djvu duality duplicity dynamic memory allocation dynamic multithreaded dynamic programming dynamic scope emacs email encryption enumeration environments ethics eval example fibonacci first class functions flang flow fork-join forms free functions garbage collection gdb geometry git glpk glpsol gmpl gpg graph graphics greedy hack haha hardware haskell health records highlight horn-clause huffman ical ikiwiki include file integer program intellectual property internet remembers issue tracking jvm lambda latex lazy lenovo lexical scope life linear programming linearization linked list linux logrotate longest common subsequence m4a makefile manners marketing matching memoization mongolia mps mst multiple compilation units mutation networking news notmuch open-source open content opencl opencourseware optimization org-mode oz packaging pdf pdftk perl photo photography pim plai plai-typed planet pointers politics preprocessor privacy programming languages pushmi python quilt quoting racket rant recursion regression rewrite rfc2822 rss sbuild scheduling scheme scope security separation shlibs shortest path simplex slashdot sorting source-highlight spam ssh stack-smash static scope strings struct substitution substitution cache superfish svn teaching test topgit topological sort tutorial types union university university computing valgrind vcs-pkg wanderlust whinge whistleblower x61 xorg y combinator yak-shaving

Welcome to my blog. Have a look at the most recent posts below, or browse the tag cloud on the right. An archive of all posts is also available.

Today I received some marketing bumpf from my employer, which on top of being a charming way to spend money while cutting my unit budget, is frankly an embarassment from the point of view of security and privacy.

Every link in this supposed communication from UNB is a link to a third party site, with the host name consisting mainly of digits. When we receive large scale phishing attacks every week so, training people to ignore funny looking urls doesn't seem like a great idea. All of these URLs contain tracking cookies, presumably so that Eloqua can sell UNB information about the mail reading habits of its employees and alumni.

It finishes with the following text.

UNB occasionally sends out important announcements to the UNB community. To unsubscribe from these emails, please click
here <http://s1961286906.t.en25.com/e/cu?s=1961286906&elqc=11&elq=my_cookie_deleted>.
To unsubscribe from all future UNB emails, please click here
Privacy Statement
UNB, the UNB Advancement Office and third party host Eloqua/Oracle are committed to protecting the personal information of
all UNB Alumni. The information collected will be used for the purposes of promoting and supporting UNB events, activities,
and endeavours and will be accessible to UNB Advancement database administrators. Connection to third party host is via
Secure Socket Layer (SSL) technology. For more information on the protection of personal information at UNB please consult
the University Secretariat, University of New Brunswick, PO Box 4400, Fredericton, NB, E3B 5A3 www.unb.ca/secretariat (506)

Can you spot the lie? Of course I mean the technical error about about http and https. What kind of cynic do you take me for?

Never mind what the government said
They're either lying or they've been misled...

Bruce Coburn, Burn, 1986

Posted Mon 14 Mar 2016 10:07:00 PM ADT Tags:

Today I was wondering about converting a pdf made from scan of a book into djvu, hopefully to reduce the size, without too much loss of quality. My initial experiments with pdf2djvu were a bit discouraging, so I invested some time building gsdjvu in order to be able to run djvudigital.

Watching the messages from djvudigital I realized that the reason it was achieving so much better compression was that it was using black and white for the foreground layer by default. I also figured out that the default 300dpi looks crappy since my source document is apparently 600dpi.

I then went back an compared djvudigital to pdf2djvu a bit more carefully. My not-very-scientific conclusions:

  • monochrome at higher resolution is better than coloured foreground
  • higher resolution and (a little) lossy beats lower resolution
  • at the same resolution, djvudigital gives nicer output, but at the same bit rate, comparable results are achievable with pdf2djvu.

Perhaps most compellingly, the output from pdf2djvu has sensible metadata and is searchable in evince. Even with the --words option, the output from djvudigital is not. This is possibly related to the error messages like

Can't build /Identity.Unicode /CIDDecoding resource. See gs_ciddc.ps .

It could well be my fault, because building gsdjvu involved guessing at corrections for several errors.

  • comparing GS_VERSION to 900 doesn't work well, when GS_VERSION is a 5 digit number. GS_REVISION seems to be what's wanted there.

  • extra declaration of struct timeval deleted

  • -lz added to command to build mkromfs

Some of these issues have to do with building software from 2009 (the instructions suggestion building with ghostscript 8.64) in a modern toolchain; others I'm not sure. There was an upload of gsdjvu in February of 2015, somewhat to my surprise. AT&T has more or less crippled the project by licensing it under the CPL, which means binaries are not distributable, hence motivation to fix all the rough edges is minimal.

Version kilobytes per page position in figure
Original PDF 80.9 top
pdf2djvu --dpi=450 92.0 not shown
pdf2djvu --monochrome --dpi=450 27.5 second from top
pdf2djvu --monochrome --dpi=600 --loss-level=50 21.3 second from bottom
djvudigital --dpi=450 29.4 bottom


Posted Tue 29 Dec 2015 12:57:00 PM AST Tags:

After a mildly ridiculous amount of effort I made a bootable-usb key.

I then layered a bash script on top of a perl script on top of gpg. What could possibly go wrong?



 keys=$(gpg --with-colons  $infile | sed -n 's/^pub//p' | cut -f5 -d: )

 gpg --homedir $HOME/.caff/gnupghome --import $infile

 caff -R -m no "${keys[*]}"

 today=$(date +"%Y-%m-%d")
 for key in ${keys[*]}; do
     (cd $HOME/.caff/keys/;   tar rvf "$output" $today/$key.mail*)

The idea is that keys are exported to files on a networked host, the files are processed on an offline host, and the resulting tarball of mail messages sneakernetted back to the connected host.

Posted Wed 23 Dec 2015 09:20:00 AM AST Tags:

Umm. Somehow I thought this would be easier than learning about live-build. Probably I was wrong. There are probably many better tutorials on the web.

Two useful observations: zeroing the key can eliminate mysterious grub errors, and systemd-nspawn is pretty handy. One thing that should have been obvious, but wasn't to me is that it's easier to install grub onto a device outside of any container.

Find device

 $ dmesg

Count sectors

 # fdisk -l /dev/sdx

Assume that every command after here is dangerous.

Zero it out. This is overkill for a fresh key, but fixed a problem with reusing a stick that had a previous live distro installed on it.

 # dd if=/dev/zero of=/dev/sdx bs=1048576 count=$count

Where $count is calculated by dividing the sector count by 2048.

Make file system. There are lots of options. I eventually used parted

 # parted

 (parted) mklabel msdos
 (parted) mkpart primary ext2 1 -1
 (parted) set 1 boot on
 (parted) quit

Make a file system

 # mkfs.ext2 /dev/sdx1
 # mount /dev/sdx1 /mnt

Install the base system

 # debootstrap --variant=minbase jessie /mnt http://httpredir.debian.org/debian/

Install grub (no chroot needed)

 # grub-install --boot-directory /mnt/boot /dev/sdx1

Set a root password

 # chroot /mnt
 # passwd root
 # exit

create up fstab

# blkid -p /dev/sdc1 | cut -f2 -d' ' > /mnt/etc/fstab

Now edit to fix syntax, tell ext2, etc...

Now switch to system-nspawn, to avoid boring bind mounting, etc..

# systemd-nspawn -b -D /mnt

login to the container, install linux-base, linux-image-amd64, grub-pc

EDIT: fixed block size of dd, based on suggestion of tg. EDIT2: fixed count to match block size

Posted Mon 21 Dec 2015 08:43:00 AM AST Tags:

I've been a mostly happy Thinkpad owner for almost 15 years. My first Thinkpad was a 570, followed by an X40, an X61s, and an X220. There might have been one more in there, my archives only go back a decade. Although it's lately gotten harder to buy Thinkpads at UNB as Dell gets better contracts with our purchasing people, I've persevered, mainly because I'm used to the Trackpoint, and I like the availability of hardware service manuals. Overall I've been pleased with the engineering of the X series.

Over the last few days I learned about the installation of the superfish malware on new Lenovo systems, and Lenovo's completely inadequate response to the revelation. I don't use Windows, so this malware would not have directly affected me (unless I had the misfortune to use this system to download installation media for some GNU/Linux distribution). Nonetheless, how can I trust the firmware installed by a company that seems to value its users' security and privacy so little?

Unless Lenovo can show some sign of understanding the gravity of this mistake, and undertake not to repeat it, then I'm afraid you will be joining Sony on my list of vendors I used to consider buying from. Sure, it's only a gross income loss of $500 a year or so, if you assume I'm alone in this reaction. I don't think I'm alone in being disgusted and angered by this incident.

Posted Fri 20 Feb 2015 10:00:00 AM AST Tags:

(Debian) packaging and Git.

The big picture is as follows. In my view, the most natural way to work on a packaging project in version control [1] is to have an upstream branch which either tracks upstream Git/Hg/Svn, or imports of tarballs (or some combination thereof, and a Debian branch where both modifications to upstream source and commits to stuff in ./debian are added [2]. Deviations from this are mainly motivated by a desire to export source packages, a version control neutral interchange format that still preserves the distinction between upstream source and distro modifications. Of course, if you're happy with the distro modifications as one big diff, then you can stop reading now gitpkg $debian_branch $upstream_branch and you're done. The other easy case is if your changes don't touch upstream; then 3.0 (quilt) packages work nicely with ./debian in a separate tarball.

So the tension is between my preferred integration style, and making source packages with changes to upstream source organized in some nice way, preferably in logical patches like, uh, commits in a version control system. At some point we may be able use some form of version control repo as a source package, but the issues with that are for another blog post. At the moment then we are stuck with trying bridge the gap between a git repository and a 3.0 (quilt) source package. If you don't know the details of Debian packaging, just imagine a patch series like you would generate with git format-patch or apply with (surprise) quilt.

From Git to Quilt.

The most obvious (and the most common) way to bridge the gap between git and quilt is to export patches manually (or using a helper like gbp-pq) and commit them to the packaging repository. This has the advantage of not forcing anyone to use git or specialized helpers to collaborate on the package. On the other hand it's quite far from the vision of using git (or your favourite VCS) to do the integration that I started with.

The next level of sophistication is to maintain a branch of upstream-modifying commits. Roughly speaking, this is the approach taken by git-dpm, by gitpkg, and with some additional friction from manually importing and exporting the patches, by gbp-pq. There are some issues with rebasing a branch of patches, mainly it seems to rely on one person at a time working on the patch branch, and it forces the use of specialized tools or workflows. Nonetheless, both git-dpm and gitpkg support this mode of working reasonably well [3].

Lately I've been working on exporting patches from (an immutable) git history. My initial experiments with marking commits with git notes more or less worked [4]. I put this on the back-burner for two reasons, first sharing git notes is still not very well supported by git itself [5], and second Gitpkg maintainer Ron Lee convinced me to automagically pick out what patches to export. Ron's motivation (as I understand it) is to have tools which work on any git repository without extra metadata in the form of notes.

Linearizing History on the fly.

After a few iterations, I arrived at the following specification.

  • The user supplies two refs upstream and head. upstream should be suitable for export as a .orig.tar.gz file [6], and it should be an ancestor of head.

  • At source package build time, we want to construct a series of patches that

    1. Is guaranteed to apply to upstream
    2. Produces the same work tree as head, outside ./debian
    3. Does not touch ./debian
    4. As much as possible, matches the git history from upstream to head.

Condition (4) suggests we want something roughly like git format-patch upstream..head, removing those patches which are only about Debian packaging. Because of (3), we have to be a bit careful about commits that touch upstream and ./debian. We also want to avoid outputting patches that have been applied (or worse partially applied) upstream. git patch-id can help identify cherry-picked patches, but not partial application.

Eventually I arrived at the following strategy.

  1. Use git-filter-branch to construct a copy of the history upstream..head with ./debian (and for technical reasons .pc) excised.

  2. Filter these commits to remove e.g. those that are present exactly upstream, or those that introduces no changes, or changes unrepresentable in a patch.

  3. Try to revert the remaining commits, in reverse order. The idea here is twofold. First, a patch that occurs twice in history because of merging will only revert the most recent one, allowing earlier copies to be skipped. Second, the state of the temporary branch after all successful reverts represents the difference from upstream not accounted for by any patch.

  4. Generate a "fixup patch" accounting for any remaining differences, to be applied before any if the "nice" patches.

  5. Cherry-pick each "nice" patch on top of the fixup patch, to ensure we have a linear history that can be exported to quilt. If any of these cherry-picks fail, abort the export.

Yep, it seems over-complicated to me too.

TL;DR: Show me the code.

You can clone my current version from


This provides a script "git-debcherry" which does the history linearization discussed above. In order to test out how/if this works in your repository, you could run

git-debcherry --stat $UPSTREAM

For actual use, you probably want to use something like

git-debcherry -o debian/patches

There is a hook in hooks/debcherry-deb-export-hook that does this at source package export time.

I'm aware this is not that fast; it does several expensive operations. On the other hand, you know what Don Knuth says about premature optimization, so I'm more interested in reports of when it does and doesn't work. In addition to crashing, generating multi-megabyte "fixup patch" probably counts as failure.


  1. This first part doesn't seem too Debian or git specific to me, but I don't know much concrete about other packaging workflows or other version control systems.

  2. Another variation is to have a patched upstream branch and merge that into the Debian packaging branch. The trade-off here that you can simplify the patch export process a bit, but the repo needs to have taken this disciplined approach from the beginning.

  3. git-dpm merges the patched upstream into the Debian branch. This makes the history a bit messier, but seems to be more robust. I've been thinking about trying this out (semi-manually) for gitpkg.

  4. See e.g. exporting. Although I did not then know the many surprising and horrible things people do in packaging histories, so it probably didn't work as well as I thought it did.

  5. It's doable, but one ends up spending about a bunch lines of code on duplicating basic git functionality; e.g. there is no real support for tags of notes.

  6. Since as far as I know quilt has no way of deleting files except to list the content, this means in particular exporting upstream should yield a DFSG Free source tree.

Posted Thu 25 Apr 2013 01:58:00 PM ADT Tags:

In April of 2012 I bought a ColorHug colorimeter. I got a bit discouraged when the first thing I realized was that one of my monitors needed replacing, and put the the colorhug in a drawer until today.

With quite a lot of help and encouragment from Pascal de Bruijn, I finally got it going. Pascal has written an informative blog post on color management. That's a good place to look for background. This is more of a "write down the commands so I don't forget" sort of blog post, but it might help somebody else trying to calibrate their monitor using argyll on the command line. I'm not running gnome, so using gnome color manager turns out to be a bit of a hassle.

I run Debian Wheezy on this machine, and I'll mention the packages I used, even though I didn't install most of them today.

  1. Find the masking tape, and tear off a long enough strip to hold the ColorHug on the monitor. This is probably the real reason I gave up last time; it takes about 45minutes to run the calibration, and I lack the attention span/upper-arm-strength to hold the sensor up for that long. Apparently new ColorHugs are shipping with some elastic.

  2. Update the firmware on the colorhug. This is a gui-wizard kindof thing.

     % apt-get install colorhug-client
     % colorhug-flash 
  3. Set the monitor to factory defaults. On this ASUS PA238QR, that is brightness 100, contrast 80, R=G=B=100. I adjusted the brightness down to about 70; 100 is kindof eye-burning IMHO.

  4. Figure out which display is which; I have two monitors.

     % dispwin -\?

    Look under "-d n"

  5. Do the calibration. This is really verbatim from Pascal, except I added the ENABLE_COLORHUG=true and -d 2 bits.

     % apt-get install argyll
     % ENABLE_COLORHUG=true dispcal -v -d 2 -m -q m -y l -t 6500 -g 2.2 test
     % targen -v -d 3 -G -f 128 test
     % ENABLE_COLORHUG=true dispread -v -d 2 -y l -k test.cal test
     % colprof -v -A "make" -M "model" -D "make model desc" -C   "copyright" -q m -a G test
  6. Load the profile

     % dispwin -d 2 -I test.icc           

    It seems this only loads the x property _ICC_PROFILE_1 instead of _ICC_PROFILE; whether this works for a particular application seems to be not 100% guaranteed. It seems ok for darktable and gimp.

It's spring, and young(ish?) hackers' minds turn to OpenCL. What is the state of things? I haven't the faintest idea, but I thought I'd try to share what I find out. So far, just some links. Details to be filled in later, particularly if you, dear reader, tell them to me.


LLVM based front ends

Mesa backend

Rumours/hopes of something working in mesa 8.1?

  • r600g is merged into master as of this writing.
  • clover

Other projects

  • SNU This project seems be only for Cell/ARM/DSP at the moment. Although they make you register to download, it looks like it is LGPL.
Posted Tue 24 Apr 2012 08:05:00 AM ADT Tags:

I've been experimenting with a new packaging tool/workflow based on marking certain commits on my integration branch for export as quilt patches. In this post I'll walk though converting the package nauty to this workflow.

  1. Add a control file for the gitpkg export hook, and enable the hook: (the package is already 3.0 (quilt))

    % echo ':debpatch: upstream..master' > debian/source/git-patches
    % git add debian/source/git-patches && git commit -m'add control file for gitpkg quilt export'
    % git config gitpkg.deb-export-hook /usr/share/gitpkg/hooks/quilt-patches-deb-export-hook

    This says that all commits reachable from master but not from upstream should be checked for possible export as quilt patches.

  2. This package was previously maintained in the "recommend topgit style" with the patches checked in on a seperate branch, so grab a copy.

     % git archive --prefix=nauty/ build | (cd /tmp ; tar xvf -)

    More conventional git-buildpackage style packaging would not need this step.

  3. Import the patches. If everything is perfect, you can use qit quiltimport, but I have several patches not listed in "series", and quiltimport ignores series, so I have to do things by hand.

    % git am  /tmp/nauty/debian/patches/feature/shlib.diff
  4. Mark my imported patch for export.

    % git debpatch +export HEAD
  5. git debpatch list outputs the following

    afb2c20 feature/shlib
    Export: true
    makefile.in |  241 +++++++++++++++++++++++++++++++++--------------------------
    1 files changed, 136 insertions(+), 105 deletions(-)

    The first line is the subject line of the patch, followed by any notes from debpatch (in this case, just 'Export: true'), followed by a diffstat. If more patches were marked, this would be repeated for each one.

    In this case I notice subject line is kindof cryptic and decide to amend.

     git commit --amend
  6. git debpatch list still shows the same thing, which highlights a fundemental aspect of git notes: they attach to commits. And I just made a new commit, so

    git debpatch -export afb2c20
    git debpatch +export HEAD
  7. Now git debpatch list looks ok, so we try git debpatch export as a dry run. In debian/patches we have

    0001-makefile.in-Support-building-a-shared-library-and-st.patch series

    That looks good. Now we are not going to commit this, since one of our overall goal is to avoid commiting patches. To clean up the export, rm -rf debian/patches

  8. gitpkg master exports a source package, and because I enabled the appropriate hook, I have the following

     % tar tvf ../deb-packages/nauty/nauty_2.4r2-1.debian.tar.gz | grep debian/patches
     drwxr-xr-x 0/0               0 2012-03-13 23:08 debian/patches/
     -rw-r--r-- 0/0             143 2012-03-13 23:08 debian/patches/series
     -rw-r--r-- 0/0           14399 2012-03-13 23:08 debian/patches/0001-makefile.in-Support-building-a-shared-library-and-st.patch

    Note that these patches are exported straight from git.

  9. I'm done for now so

    git push 
    git debpatch push

the second command is needed to push the debpatch notes metadata to the origin. There is a corresponding fetch, merge, and pull commands.

More info

Posted Tue 13 Mar 2012 08:04:00 AM ADT Tags:

I have been in the habit of using R to make e.g. histograms of test scores in my courses. The main problem is that I don't really need (or am too ignorant to know that I need) the vast statistical powers of R, and I use it rarely enough that its always a bit of a struggle to get the plot I want.

racket is a programming language in the scheme family, distinguished from some of its more spartan cousins by its "batteries included" attitude.

I recently stumbled upon the PLoT graph (information visualization kind, not networks) plotting module and was pretty impressed with the Snazzy 3D Pictures.

So this time I decided try using PLoT for my chores. It worked out pretty well; of course I am not very ambitious. Compared to using R, I had to do a bit more work in data preparation, but it was faster to write the Racket than to get R to do the work for me (again, probably a matter of relative familiarity).


#lang racket/base
(require racket/list)
(require plot)

(define marks (build-list 30 (lambda (n) (random 25))))

(define out-of 25)
(define breaks '((0  9) (10 12) (13 15) (16 18) (19 21) (22 25)))

(define (per-cent n)
  (ceiling (* 100 (/ n out-of))))

(define (label l)
  (format "~a-~a" (per-cent (first l)) (per-cent (second l))))

(define (buckets l)
  (let ((sorted (sort l <)))
    (for/list ([b breaks])
          (vector (label b)
           (count (lambda (x) (and 
                    (<= x ( second b))
                    (>= x ( first b))))
  (buckets marks)))
 #:out-file "racket-hist.png")
Posted Fri 24 Feb 2012 10:02:00 PM AST Tags:

This wiki is powered by ikiwiki.