lzjwm ascii compression algorithm

I needed an ascii compression algorithm that was extremely tiny, allowed random access, and could uncompress data with no memory overhead for embedded systems. This is what I came up with. It is similar to lzss compression except the offset is in compressed space rather than character space. so the anemic 5 bit pointer can actually stretch pretty far in character space and copy from hundreds of characters away.

more information as well as a discussion of the theory can be found here

github repository

OneWheel Cargo Net

Simple cargo net made with some grommets and shock cord. Mostly to make my OneWheel visually distinctive but it can free up a hand.

Optimizing power consumption on an OLED laptop

I spent some time optimizing my Linux laptop (Thinkpad X1 Yoga 1st gen) for power usage and the results were a dramatic improvement in battery life. One of the most amazing features of this laptop is the absolutely beautiful OLED display. Since OLEDs only consume power when emitting light, showing a white screen takes much more power than a dark screen. I used ‘powertop’ to help optimize my ubuntu 18.04 system as much as possible and ran it in two runs with a full battery. The _only_ difference between the two was one running in a maximized xterm with a white background and the other was running in a maximized xterm with a black background. Here are the results next to each other.

The change was dramatic. almost a 15 hour battery lifetime with a black background vs a 4 and a half hour one with a white background. Since I spend 90% of my time in a full screen xterm or vim window with black background this translates into the longest practical battery life I have ever gotten out of a laptop. For some reason Lenovo has discontinued the OLED option, but they can still be found second hand.

(the irony of my web site having a white background is not lost on me. I need to spend some time fixing that.)

full screenshots so you can see there are no shenanigans.

whaw 0.3 released

whaw 0.3 has been released. whaw is a window tiling system for xwindows that is independent of the underlying window manager allowing you to add basic tiling to any window manager.

The major new features are that it can now be triggered in one shot mode, for instance from a keybinding, it now handles maximized windows properly for fluxbox, and when you press shift while clicking on a window, it will give it more room than it would otherwise.

I have also started mirroring certain projects on github however development is still done via darcs.

http://repetae.net/computer/whaw

Circular mirror idea for laser lithography

I have been working on using a laser to directly expose photosensitive PCBs for etching using a modified version of Henner Zeller’s design in the ldgraphy project. One of the major issues is that the focal point of the laser changes as it sweeps across the PCB, impacting the minimum feature size that can be etced. There are various solutions given in the design document however the best one, a circular mirror is currently not used.

Continue Reading »

DSO Shell – A neat little kit scope.

The jyetech DSO Shell is a pretty neat little toy oscilloscope kit. It can only go to 100khz or so and is single channel, but it is actually fairly useful sometimes. Also, the fact it comes with schematics and source code is great for learning how scopes work.

The main issue with it is that it requires external power via a DC jack, which can be a pain. Like many people I decided to add a battery pack to mine. Not the prettiest, but it does give the scope a nice heft to it.

Here is a link to the scope: http://www.jyetech.com/Products/LcdScope/e150.php

Here is my album of adding the battery pack: DSO Shell

Painless IPSec setup for a home network.

I have written a script to painlessly set up fully secured encrypted network traffic between systems on a small LAN or home network. Although more specialized than other IPSec solutions such as SWAN or Racoon, it does provide for the common use case of securing otherwise sensitive protocols such as nfs, dns, web based device configuration pages, and samba that are often sent in the clear or with minimal authentication.

Network security has always been something of a pain, different protocols require completely different systems that must be independently learned and implemented. A signed certificate for https, a kerberos server for secure NFS, the woefully uncommon DNSSEC for DNS as well as many protocols that have no easy way to add security other than piggybacking on something such as SSH or stunnel.

IPSec makes all of this a non-issue. All traffic between hosts is encrypted and verified, no matter what the underlying protocol is. The encryption and verification is done in the kernel and is fully transparent to apps. Unfortunately, it also can be a bit complicated to set up in general due to the need for a daemon to handle the public key exchange, However for the common case of secure communications within a LAN between known hosts a lot of the usual complications can go away since you can pre-distribute the keys beforehand resulting in a simpler setup. I have written a script to automate this process.

Continue Reading »

Cuckoo Byte Stuffing Algorithm

Cuckoo Byte Stuffing

I introduce a byte stuffing algorithm for general use that has many useful properties that are not found together in other common algorithms. It obtains very low statistical overhead on arbitrary data without signifigantly increasing the entropy of the data stream. It does this by permuting the escape characters, taking them from a PRNG stream, rather than modifying the raw data. This means that the compressibility and radix locality of the encoded stream is preserved.

Similar to Cuckoo Hashing the algorithm has a pair of escape codes at any time from which values are ejected and a new one is chosen when they are shown to increase the size of the coded stream. By only ejecting a choice for an escape character on conflict, the algorithm is self optimizing, when the symbols of the data stream are not uniformly distributed, cuckoo stuffing achieves greater than the maximum theoretical efficiency  for random data. In particular, ASCII and UTF8 data have zero overhead for arbitrarily long streams even when they contain embedded null characters.

  • True online operation requiring zero bytes of lookahead, data can be output as soon as it is generated. By adding a single byte of lookahead the average size overhead can be further reduced. Said lookahead can be done opprotunistically based on data availability without changing the decoder.
  • The encoded byte stream preserves locality and compressibility, long runs of similar values remain long runs of similar values in encoded form. When possible, the stream remains unchanged aiding debugging by hardware protocol analyzers. This means that the encoded stream may directly be used as a radix tree key with the same efficiency as the unencoded stream.
  • Worst case 2x overhead but average case 0.2%, On any form of structured data with a non uniform distribution, the overhead asymptotically approaches zero. unlike other probabalistic algorithms the average case is over arbitrary data, not just random data. There are no generic pathological patterns to exploit.
  • The encoding/decoding algorithm requires only 7 bytes of RAM and no buffer. An implementation that takes only about 100 words of program memory on an atmega 8 bit mcu is provided. The PRNG is chosen to be particularly fast on both 8 bit and 32/64 bit architectures. Coding is extremely fast as PRNG only needs to be run on the rare collision.
  • Sample implementation released under completely free open source BSD style license.

Algorithm

Encoding takes a byte stream with arbitrary binary data and produces a byte stream that never has a byte equal to zero within it. Decoding inverts this process.

The algorithm relys on a PRNG that can generate a random sequence of bytes. At any given point, there are two escape codes active, e1 and e2. e1 is used to replace the zero byte, e2 is used to indicate that a literal e1 or e2 needs to be inserted. When a literal e1 or e2 occurs in the stream, it is replaced by the sequence e2 e1 or e2 e2 respectively and a new escape value is chosen by iterating the PRNG until the next number that is not zero and not equal to the other escape code. A new code is chosen only when a two byte escape code is generated.

Bytestream format

The decoding rules are as follows:

e1 -> 0
e2 e1 -> e1  and replace e1 with next code in sequence.
e2 e2 -> e2  and replace e2 with next code in sequence.
e2 x | x not in {e1,e2} -> e2 x
x -> x

The encoding rules are the opposite:

0 -> e1
e1 -> e2 e1  and replace e1 with next code in sequence.
e2 x | x not in {e1,e2,0} -> e2 x
e2 -> e2 e2  and replace e2 with next code in sequence.
x -> x

Specifics

The PRNG chosen is based on an 8 bit xorshift algorithm, It performs very well on the Diehard tests and although specified as an 8 bit algorithm, it admits a particularly fast implementation on 32 or 64 bit architectures where the 4 middle ops can be replaced by a single shift in a full register.

#define INIT_CODE_STATE {  .x = 21, .y = 229, .z = 181, .w = 51 }
struct ecode_generator_state { uint8_t x, y, z, w; };

uint8_t
next_ecode(struct ecode_generator_state *s, uint8_t verboten)
{
        do {
                uint8_t t = s->x ^ (s->x << 3);
                s->x = s->y; s->y = s->z; s->z = s->w;
                s->w = s->w ^ (s->w >> 5) ^ (t ^ (t >> 2));
        } while (!s->w || s->w == verboten);
        return s->w;
}

The initial values for E1 and E2 are

#define INIT_E1 0xC1
#define INIT_E2 0xF8

These were chosen to give a good chance of zero overhead on common data streams.

  • Neither occurs in ASCII
  • Neither will ever appear in valid UTF8 data
  • Do not correspond to any common pad values in binary data protocols

Code

Optimizing Haskell compiler jhc 0.8.1 is out

A new version of the jhc optimizing haskell compiler has been released with a new licence, new libraries, and lots of improvements.

After a long hiatus, I have released a new version of my haskell compiler jhc.

http://repetae.net/computer/jhc

  • New license, jhc is now released under a permissive BSD style licence rather than the GPL. The license is compatible with that of ghc allowing code mixing between them.
  • New library layout based around the standards, there are now haskell98 and haskell2010 packages that are guarenteed to be future proof strictly compatible with the respective standards. A package haskell-extras contains the additonal libraries from ghc’s base.
  • Native support for complex and vector SIMD primitives, exposed via type
    functions. for instance ‘foo :: Complex_ Float32_’ for hardware accelerated
    complex 32 bit floats for instance. These are unboxed only for now, full
    library Num support in the works.
  • support for android as a target, you must install the android NDK to use this.
  • Support for embedded ARM architectures imported from Kiwamu Okabe’s branch
    allowing targeting bare hardware with no OS.
  • user defined kinds, introduced with the ‘kind’ keyword otherwise looking like
    ‘type’ declarations.
  • export/import lists now allow namespace qualifiers kind, class, type, or data
    to explicitly only import or export the specific named entity. As an
    extension allowed by this, classes and types no longer are in the same
    namespace and can share names.
  • ForeignPtr’s now have working finalizers when collected by the RTS.
  • CTYPE pragma to allow promoting arbitrary C types to FFIable entities.

Whaw 0.2 released.

Window tiling is nice; automatically placing your windows to not overlap and maximally use screen space. Switching fully to tiling window managers is not always feasible. Whaw is a program I wrote to tile windows on your screen completely independently of your window manager. It plays nicely with anything from modern window managers to using no window manager at all, calculating the proper arrangement then sending commands to your manager to carry out the placement.

 

Get it at  http://repetae.net/computer/whaw/