Cross compiling libjpeg-turbo targeting ARM for software jpeg compression

In a quest to get faster software jpeg compression on ARM I cross compiled libjpeg-turbo 1.3.0 and pitted it against standard libjpeg (libjpeg-turbo can be used as a drop in replacement for libjpeg). For 24bit rbg images of size 4096×2000, libjpeg-turbo was about twice as fast as libjpeg. Here’s how I compiled libjpeg-turbo:

First get the source:


Then un-tar it and cd into the main source directory. Then configure for ARM:

 ./configure --host=arm-linux-gnueabi CC=arm-linux-gnueabi-gcc AR=arm-linux-gnueabi-ar \
          STRIP=arm-linux-gnueabi-strip RANLIB=arm-linux-gnueabi-ranlib \

And make:

make install

The output files will be put under the directory that you specified when you configured, copy them onto your ARM device as appropriate.

New batteries for my Casio fx-580

The Software Engineer’s mate – a really good scientific calculator, I have just refreshed the batteries in my Casio fx-580, I still haven’t found as good a calculator even though it of 80’s vintage!

The keys are a bit ‘yellowed’ now, bit otherwise its powering along.


New Scientist Enigma 1780 and Python

Python program to solve New Scientist Engima 1780
Sometimes a body has to take a break from all this Software Engineering stuff and instead delve into some recretional programming, so with this in mind I decide to see if I could write a small python program to solve the New Scientist Enigma #1780. This enigma is kind of like suduku on an icosahedron of all things (a 20 faced thing).

Anyway it was just for fun and I wasn’t looking for the ‘best’ or most ‘elegant’ solution to the problem, just one that kinda worked! So I wrote a little program over Christmas which I got working (more or less).

I enjoyed the challenge decided to try my hand at future enigmas – only to find out that Enigma #1780 was the last one ever, the New Scientist is giving them up – which is a great pity seeing as I have only started to get interested in them.

Today I came across this site which has python solutions for tonnes of Enigmas including 1780, it was on this site that I learned that 1780 is the last enigma. They point out that there is a large archive of enigmas.

In an attempt to codify the puzzle, I decided think about the flattened out icosahedron (its net) as a grid of 4 rows of 5 triangles, in this way an individual triangle can be referenced using a pair of numbers (i, j), where i varies between 0 and 4 and specifies the triangle’s ‘column’ while j specifies its row. Next I tried to come up with some rules that would find the coordinates of all of the triangles ‘connected’ to the triangle at (i, j).

Once all of that is done solving the puzzle given a valid input net is a matter of finding an empty triangle, finding the set of numbers that can go into that triangle, picking one of these numbers and recursively solving the puzzle for the update net, if the recursive solve fails for that number we try the next number and so on….

Anyway, the solve() function is called like this:

solve(start_net, 0)
# Try to solve New Scientist Enigma 1780 (the last one!)
# Run like:
# solve(start_net, 0)
all_values = {1, 2, 3, 4, 5}
net_width = 5
net_height = 4;
# get the value at (i, j)
def value_at(net, a):
    i, j = a
    return net[i + j * net_width]
# set the value at (i, j)
def set_value_at(net, a, val):
    i, j = a
    net[i + j * net_width] = val

# Create list to hold net values, initialised with zeros
start_net = [0] * (net_height * net_width)
# insert the starting values
set_value_at(start_net, (0,0), 2)
set_value_at(start_net, (0,1), 5)
set_value_at(start_net, (0,3), 1)
set_value_at(start_net, (4,0), 4)
#set_value_at(start_net, (4,2), 3)
set_value_at(start_net, (4,3), 2)

# loop i around if i > net_width (modulo)    
def mi(i):
    return i % net_width
# The connection rules for each row
i_0 = [lambda i: (mi(i+1), 0), lambda i: (mi(i+2), 0), lambda i: (mi(i+3), 0), lambda i: (mi(i+4), 0), lambda i: (mi(i-1), 1),
       lambda i: (mi(i-1), 2), lambda i: (mi(i), 1), lambda i: (mi(i+1), 2), lambda i: (mi(i+1), 1)]
i_3 = [lambda i: (mi(i+1), 3), lambda i: (mi(i+2), 3), lambda i: (mi(i+3), 3), lambda i: (mi(i+4), 3), lambda i: (mi(i-1), 2),
       lambda i: (mi(i), 1), lambda i: (mi(i), 2), lambda i: (mi(i+1), 1), lambda i: (mi(i+1), 2)]
i_1 = [lambda i: (mi(i-1), 0), lambda i: (mi(i-1), 1), lambda i: (mi(i-1), 2), lambda i: (mi(i-1), 3), lambda i: (mi(i), 0),
       lambda i: (mi(i), 2), lambda i: (mi(i), 3), lambda i: (mi(i+1), 0), lambda i: (mi(i+1), 1)]
i_2 = [lambda i: (mi(i), 0), lambda i: (mi(i), 1), lambda i: (mi(i), 3), lambda i: (mi(i-1), 2), lambda i: (mi(i-1), 3),
       lambda i: (mi(i+1), 0), lambda i: (mi(i+1), 1), lambda i: (mi(i+1), 2), lambda i: (mi(i+1), 3)]
cons = [i_0, i_1, i_2, i_3]
# is a connected to b?
def connected(a,b):
    (i, j) = a
    if a == b:
        return True;
    return b in [d(i) for d in cons[j]]
# gets a list of all triangle coordinates
def all_triangles():
    return [(i % net_width, i // net_width) for i in range(0,net_height*net_width) ]
# gets a list of all triangles connectd to a    
def connected_triangles(a):
    return [b for b in all_triangles() if connected(a,b)]
def find_loc_of_first_empty_triangle(net):
        index = net.index(0)
        return (index % net_width, index // net_width)
        return None 
# returns a list of all empty triangles
def all_empty_triangles(net):
    return [a for a in all_triangles() if value_at(net, a) == 0]
# returns the possible values (1..5) that can go into
# the triangle a
def possible_values(net, a):
    ct = connected_triangles(a)
    used_values = {value_at(net, t) for t in ct}
    return all_values - used_values - {value_at(net, a)}
# solve given a valid input net    
def solve(net, depth):
    print ('solve, depth: ' + str(depth))
    a = find_loc_of_first_empty_triangle(net)
    # if there are no free locations then the
    # net if full and we have finished
    if not a:
        print ('net is full ' + str(net))
        return net
    # get list of possible values for this triangle
    possible = possible_values(net, a)
    # If we can't make a move then we need
    # to backtrack
    if not possible:
        print ('No more possible moves for ' + str(a))
        return []
    for v in possible:
        # create a copy of our current net
        new_net = list(net)
        set_value_at(new_net, a, v)
        result_net = solve(new_net, depth+1) 
        if result_net:
            return result_net
    return []
if __name__ == "__main__":
    res = solve(start_net, 0)

Update, 07/02/2014
The answer to this Enigma as announced here is: 324125, thankfully the same as that announced by the Python program! Unfortunately I didn’t win the competition, but I had loads of fun trying to write some software to solve it! I might try a Haskell version next if I find the time…

sed: unsupported command e

If, when you try to use sed command to do a search and replace you get the following error:

sed: unsupported command e

Then you may have forgotten to include ‘s’ at the start of the command, e.g. this will produce the error:

sed  -i '/^server\s\+\S\+$/server' test.conf

While this will work ok (note the all important ‘s’):

sed  -i 's/^server\s\+\S\+$/server' test.conf

PS Happy New Year!