Bit Twiddling abs() with GCC

Recently on Reddit there was a link to a page which listed a lot of clever “bit twiddling” hacks. I decided to try the hack for computing abs() against the standard library function and the naive implementation:

/* Clever version */
static inline int32_t
abs_1(int32_t v)
{
    const int32_t m = v >> sizeof(int32_t) * 8 - 1;
    return (v ^ m) - m;
}

/* Naive version */
static inline int32_t
abs_2(int32_t v)
{
    return v < 0 ? -v : v;
}

Compiling with gcc -O3 produces exactly the same code for all three versions!

  c1 fa 1f    sar    $0x1f,%edx
  31 d0       xor    %edx,%eax
  29 d0       sub    %edx,%eax

If I also specify -march=athlon-xp to optimize for my processor, the sar instruction is replaced with cltd (also known as cdq).

  99          cltd
  31 d0       xor    %edx,%eax
  29 d0       sub    %edx,%eax

Script: check_dvd

The main operating system I use is Arch Linux. My favourite feature of the distribution is the package management system which, although glacially slow and insanely inefficient, makes it very easy to make your own packages and has quite a lot of obscure but useful packages in the AUR. I am still using the original installation (version 0.5 if I remember correctly) which I have continually kept up-to-date with pacman. The distribution has undergone several big changes (such as switching from devfs to udev) and many small ones which sometimes go undetected. The accumulation of old cruft (such as out-of-date configuration files) means that things don’t work as well as a fresh installation unless you are willing to spend hours tracking down every little change.

For example, K3B used to correctly re-insert and check a DVD after burning but now it just hangs waiting for the tray to close (closing the tray does not help). So I wrote a little script to help me check DVDs. It takes a list of directories and checks the contents of the DVD against files with the same name in those directories. It does not scan recursively since I use this mainly for large video files which I put on the top-level directory of the disc.

#!/bin/bash

DVD=/mnt/dvd

if [ $# -le 0 ]; then
    echo “usage: $0 DIRS…”
    exit 1
fi

mount | grep $DVD >/dev/null || mount $DVD
pushd $DVD >/dev/null

for file in *; do
    for dir; do
        if [ -f "$dir/$file" ]; then
            echo “checking: $file”
            diff “$DVD/$file” “$dir/$file” >/dev/null
            if [ $? -ne 0 ]; then
                echo “*** error in file: $file”
            fi
        fi
    done
done

popd >/dev/null
umount $DVD

I really should just fix the problem with K3B :-)

Edit: It’s a bug in K3B. Thankfully there is a simple workaround.

Argument decoupling in concatenative languages

An interesting point about so-called concatenative languages is the decoupling of arguments from procedure calls due to the stack. Here is a simple example:

  : foo ( x c -- x' ) if bar else baz then ;  ( Forth )
  : foo ( x c -- x' ) [ bar ] [ baz ] if ;    ( Factor )

The word foo selectively executes bar or baz depending on the value of the condition argument. Notice the argument x is decoupled from the application of bar or baz.

The applicative example might be:

  (define (foo x c)
    ((if c bar baz) x))   ; Scheme

This procedure is equivalent to the Forth word, but is subtly different. The conditional expression evaluates to a procedure value (bar or baz) which is then used inside the application expression. The Forth version does not evaluate the words as values, it simply executes them directly!

What if we wanted to change the definition of baz so that it takes two arguments. Say we want to give it x twice, we could change the definition to:

  : foo ( x c -- x' ) if bar else dup baz end ;  ( Forth )
  : foo ( x c -- x' ) [ bar ] [ dup baz ] if ;   ( Factor )

Very easily done. In Scheme we would have to change the procedure to:

  (define (foo x c)
    (if c (bar x) (baz x x)))   ; Scheme

Which now means we have to use two separate application expressions, or a more direct translation:

  (define (foo x c)
    ((if c bar (lambda (a) (baz a a))) x))   ; Scheme

Which is quite bizarre and forces us to create a superfluous lambda. Both solutions are unpleasant and I expect most people would opt for the first version for clarity.

There are advantages and disadvantages to this decoupling. On the plus side, it allows greater factoring opportunities and conciseness. But we pay for this by having to deal with the complexity of stack management and reduced readability since it is not obvious at-a-glance what arguments feed into what words.

Is it possible to invent a syntax which combines the advantages of applicative and concatenative languages? I would really like to see what that would look like.