eink algorithmic art shell scripting

[kaminkatze]

Originally Posted by geekmaster

The easiest is to ASSUME that the kindle has 300 byte-wide pixels per line, with values "dd if=$DZ of=$DF ..." or "echo -e '\xff'|dd of=$DF ...".

Something like this:

Spoiler:

#!/bin/sh

#===========================
# cleanup - delete tmp files
#---------------------------
trap 'cleanup ; exit' SIGINT SIGTERM
cleanup() {
  rm $DL $BF
}

#===========================
# initvar - init global vars
#---------------------------
initvar() {
  XF=140 XL=160 YF=190 YL=210
  DN=/dev/null DF=/dev/fb0 BF=$(mktemp "/tmp/tempXXXXXX") LL=300
  D='0' L='F' DD=/dev/zero DL=$(mktemp "/tmp/tempXXXXXX")
  echo -ne "\xFF" >$DL
  eips -c
  for x in $(seq $((XF-2)) $((XL+2))); do
    setpix $x $((YF-2)); setpix $x $((YL+2))
  done
  for y in $(seq $((YF-2)) $((YL+2))); do
    setpix $((XF-2)) $y; setpix $((XL+2)) $y
  done
}

#===========================
# usage: load x y name
#---------------------------
load() {
  local x=$((XF+$1)) y=$((YF+$2)) name=$3
  case "$name" in
  glider)
    setpix $((x+1)) $y
    setpix $((x+2)) $((y+1))
    setpix $x $((y+2))
    setpix $((x+1)) $((y+2))
    setpix $((x+2)) $((y+2)) ;;
  esac; eips ''
}

#===================================
# usage: setpix x y
#-----------------------------------
setpix() {
  local x=$1 y=$(($2*2))
  dd if=$DL of=$DF bs=1 count=1 seek=$((y*LL+x)) 2>$DN
  dd if=$DL of=$DF bs=1 count=1 seek=$(((y+1)*LL+x)) 2>$DN
}

#===================================
# update - update field
#-----------------------------------
update() {
  local b m t c v
  cat $DF > $BF
  for x in $(seq $XF $XL); do
  for y in $((YF-1)) $YF; do y=$((y*2))
    m=$b b=$(hexdump -v -s $((y*LL+x-1)) -n 3 -e '/1 "%X"' $BF)
  done
  for y in $(seq $YF $YL); do y=$((y*2))
    t=$m m=$b b=$(hexdump -v -s $(((y+2)*LL+x-1)) -n 3 -e '/1 "%X"' $BF)
    c=$(expr length "$b$m$t")
    v=$(hexdump -s $((y*LL+x)) -n 1 -e '"%X"' $BF)
    if [[ $v == $D ]]; then
      [[ $c -eq 12 ]] && v=$DL || v=$DD
    else
      [[ $c -lt 12 -o $c -gt 13 ]] && v=$DD || v=$DL
    fi
    dd if=$v of=$DF bs=1 count=1 seek=$((y*LL+x)) 2>$DN
    dd if=$v of=$DF bs=1 count=1 seek=$(((y+1)*LL+x)) 2>$DN
  done; done; eips ''
}

#===================================
# loop - update loop
# usage: loop steps
#-----------------------------------
loop() {
  local c=$1 p=0 t0=$(date +%s) t1
  eips "Generation: 0"
  while [[ $p -lt $c ]]; do
    update; p=$((p+1))
    t1=$(date +%s)
    eips "Generation: $p ($((t1-t0))s)"
    t0=$t1
  done
}

initvar
load 2 2 glider
loop 100
cleanup

Originally Posted by geekmaster

Another option I thought of was to use a 600-byte wide /tmp/buffer (to hold a scan line for both touch/k4 8-bit pixels or the k3/dx 4-bit pixels) and then for the k3/dx draw 4 different pixel pair bytes to the framebuffer based on the values (\x00 \xf0 \x0f \xff).

Any hints on how to condense the line? I tried some things with awk but had problems with \x00 in the input. (Never used awk before so this could be entirely my fault.)

[geekmaster]

Originally Posted by kaminkatze

Any hints on how to condense the line? I tried some things with awk but had problems with \x00 in the input. (Never used awk before so this could be entirely my fault.)

For the K4 and Touch, I used value \x01 instead of \x00, which truncates to \x00 inside the eink kernel mode drivers. For a K3 or DX, this could be a slight speed problem because ANY grayscale that is drawn or overwritten makes the eink drivers choose a slower update algorithm to support grayscale.

When using "dd" it is a LOT easier and faster to just copy \x00 from /dev/zero (see the "tangle" demo above, which draws both black and white on a K3 eink display). Pure black and white is MUCH faster with smoother animation.

I plan to implement a particle animation system (and a Chipmunk Physics port) when I switch to using C for my kindle native mode GUI creations.

P.S. I will check out your code later. Busy now...

EDIT: Checkout the "tangle" script a few posts back. I did it for you, as an example of how you can have fast small filled objects to populate occupied grid elements for your gliders (and other "life" constructs). I did triangles just to get an example out there so you can see just how fast it is, but you should modify the midpoint circle algorithm used in "spoxbrane" instead. This example draws both black and white filled areas, for a Kindle 3. And check out PoP's Kindle 3 backport of "rippleweave" to see another example of double-wide pixels like I am using in "tangle". Good luck!

[kaminkatze]

Originally Posted by geekmaster

Checkout the "tangle" script a few posts back. I did it for you, as an example of how you can have fast small filled objects to populate occupied grid elements for your gliders (and other "life" constructs). I did triangles just to get an example out there so you can see just how fast it is, but you should modify the midpoint circle algorithm used in "spoxbrane" instead.

I did. Thanks for your scripts and inspiration. In fact, I did modify the midpoint circle to a filled circle, but with the slow pixel merging code. (Only drawing the first and last byte in a line with half byte precision and fill the rest with dd.) Worked great but I wanted to try it pixel wise.

Now I'm nearly convinced that I can't come up with any shell script that updates the full 600x800 in a few seconds.

[geekmaster]

Originally Posted by kaminkatze

Now I'm nearly convinced that I can't come up with any shell script that updates the full 600x800 in a few seconds.

The speed problem isn't just the shell script. A LOT of time is consumed by the eink display drivers, especially with the default update mode used by the eips command. You have more control using ioctl() calls from a C program, but even then, if the "dirty area" between update calls is too large, the drivers switch to a "deferred update" mode where they preferentially draw black pixels, but delay drawing white pixels for up to two seconds. They can also detect and update two smaller "dirty" areas inside a larger area.

When you do a LOT of fast updates, the eink drivers create some interesting time-domain artifacts on the display, as an emergent property of the mix of update algorithms they use to blend speed and quality in an algorithmic sort of way.

To get any kind of speed for animation playing in an active window on the screen, I had to make my window about 360x240 pixels (think old-school DivX movies ). Any larger and the display updates become unpleasant for animation.

I found that the best thing to do is use only black and white pixels, with spatial dithering to create perceived grayscale in images. There are trade-offs all around, and it is necessary to adjust your program to compensate for them.

Display updates will be a lot more predictable when I can replace the kernel mode eink drivers with my own code that talks directly to the bare eink controller chips (in a custom u-boot image to begin with, and later in a custom linux kernel). I can now run custom u-boot image files with MfgTool, and custom kernel image files with kexec (see other threads).

Again, we are only limited by our imaginations.

P.S. On the K3, eips is MUCH slower than on the K4 and Touch, so you should call it only in the outermost loop (perhaps updating the entire screen, in some cases, instead of individual cell updates). You really need to try different update speeds to see which works best. In one of my programs, I examine a timer variable in my main program loop, and only do display updates about 5 to 12 times per second using ioctl() calls on a K3 (whatever gives the most pleasing effect for the amount of screen changes I am using). I have not gotten ioctl() calls to work right on the K4 or touch yet, but eips is MUCH faster on them, so I even call it with system("eips ''); calls from C programs, and I did not get ioctl() calls working right on the newer kindles yet (no urgency).

[geekmaster]

vidtest

Don't be too discouraged about speed. You can still do some interesting things. Here is something I did called "vidtest", to test video on a K3 back in October of last year (see attached file). This is just a binary executable that runs on a K3. I need to clean up the C source code before I publish it (being a "test framework", it contains much more obsolete "commented out" code than current active code). UPDATE: It has been cleaned up and published as the "sparkle" demo" in another thread for C demo programs.

The K4 and Touch have much faster display update algorithms, so I am looking forward to programming them in C with performance as good as or better than how this video test program runs on the K3.

When you run this program on a K3, you can see what I was talking about when I mentioned the "time domain artifacts" from the kernel-mode display driver eink update algorithms.

Do you see how fast those pixels are being updated in 4-bit (600 pixel wide) mode? I am looking forward to seeing them updated using Conway's Life algorithm!

EDIT: The choice of programming language is rarely the problem. You just need to "think differently" and find a better algorithm. You should read Jon Bentley's nice little "Programming Pearls" books. They are quick reads and wonderful sources of software inspiration!

[kaminkatze]

Originally Posted by geekmaster

EDIT: The choice of programming language is rarely the problem. You just need to "think differently" and find a better algorithm.

Yeah, but with arrays vs. starting a (series of) new process(es) for every pixel access, this might be one of the rare cases. Maybe I do a pure sh version with smaller grid, if I'm lucky enough to find a good solution. Definitely keeping my eyes open.

Originally Posted by geekmaster

Do you see how fast those pixels are being updated in 4-bit (600 pixel wide) mode? I am looking forward to seeing them updated using Conway's Life algorithm!

For today only the linear array style. Thus no wrap around on top/bottom.
It initializes the array with the thresholded framebuffer content.

[geekmaster]

"Normal" shell arrays did not work for me, but substrings work.

You can put thousands of chars into a var like I do with the K3 black pixels (or K4/touch white pixels) in $B in the "tangle" script. Then access them with ${B:$((y*width+x)):1} and just use different chars for your data. Or you can make the width :2 instead :1 and double the width for larger array values. EDIT: I only tested the substring access on a touch, and we leaned later that it is not supported on the K3, so the older "echo and cut" method would be needed on a K3. This is not as bad as it would seem because echo and cut are busybox built-ins, and we are already running the busybox shell, so echo and cut would already be memory-resident.

At least that way there is no external RAMdisk access using hexdump and/or dd...

Of course, no '\x00' inside the string, but it seems to hold other binary data okay. You can use just characters to represent cell states, and use them in a case...esac after extracting them from the storage string. To replace a character at position 100 in the string with a new value in $N, I would do something like:

a=${B:1:99}; c=${B:101}; B=$a$N$e

... and you can get the length of $B with ${#B}

I just tested this by storing about 2 million chars in my $B, and extracting selected characters. It worked. So just store your "database" in a string var instead of a file on /tmp. At least I would try that and see if it is faster.

I find it fascinating that you can store megabytes in a string var, as long as it contains no NULL chars (\x00). I am going to try storing a whole framebuffer in a string (with \x00 changed to \x01, which is fine for a K4 or touch, but would reduce blacks to dark gray on on K3).

And when using a K3, you do not need to call the eips program (but you do for the K4 and touch). Instead, on the K3 and older, you can update the display the "old fashioned" way:

echo 1 > /proc/eink_fb/update_display

That would save having to call the external eips program as an external process.

EDIT: I was just about to examine your "script", but it starts with "ELF" -- so you decided to do C, eh? I just ran it. Considering that you are updating the entire display, 4 to 5 fullscreen updates is all the faster the eink can do. If you change a smaller window on the display, you can get about 12 frames per second updates, on the eink Pearl display (the older DX eink is a lot slower).

You are at the limits of the display technology here. If you want more speed you need to reduce the size of your active pixel grid on the display. The size I used on my "vidtest" demo was about the largest I could use on a K3 without slowing down the eink display refresh rate.

What I would do is use a smaller update area, but surround that with a nice ornate "picture frame" that does not change and therefore does not slow down the display...

*** Good job! ***

I would like to use your source code if you don't mind... Is it available for download somewhere?

[geekmaster]

Originally Posted by kaminkatze

Yeah, but with arrays vs. starting a (series of) new process(es) for every pixel access, this might be one of the rare cases. Maybe I do a pure sh version with smaller grid, if I'm lucky enough to find a good solution. Definitely keeping my eyes open.



For today only the linear array style. Thus no wrap around on top/bottom.
It initializes the array with the thresholded framebuffer content.

You could try keeping the entire framebuffer in a string, and write it to the framebuffer in one large chunk.

But we *are* getting into areas where after prototyping a proof-of-concept in shell script, better performance may require a compiled language. But then again, the eink display is the limiting factor, so perhaps we can make faster shell scripts...

Part of the reason for doing this in /bin/sh is to get people involved who may not be ready for a compiled language, and to prove that we CAN do more than we think even with very primitive tools.

[kaminkatze]

Originally Posted by geekmaster

"Normal" shell arrays did not work for me, but substrings work.

I have one preliminary version lying around which uses a string variable to store the data.
Needs some polishing before I can post it.

Originally Posted by geekmaster

What I would do is use a smaller update area, but surround that with a nice ornate "picture frame" that does not change and therefore does not slow down the display...

Ok, I'll add options for field size and picture save games.
Update a smaller area means I have to use the ioctl() calls?

Originally Posted by geekmaster

I would like to use your source code if you don't mind... Is it available for download somewhere?

I'll include it in the next update.

[geekmaster]

Originally Posted by kaminkatze

I have one preliminary version lying around which uses a string variable to store the data.
Needs some polishing before I can post it.


Ok, I'll add options for field size and picture save games.
Update a smaller area means I have to use the ioctl() calls?


I'll include it in the next update.

When this is "polished" and source included, I will add a link to your post from the first post in this thread, where I am putting announcements. I have some 800x600 "touchpaint 2.0" code that I need to polish myself so I can publish it, so you are not alone...

[geekmaster]

I need to fix a touchscreen event handing bug, before my touchpaint 2.0 script (with 600x800 multi-touch support) is ready to publish here.

I want my kindle native-mode GUI tutorial scripts as simple as possible, but my newly developing multi-touch support keeps trying to grow on me. I need multi-touch support so I can use two-finger pinch, stretch, and rotate touchscreen gestures to resize and rotate onscreen objects in "real-time", but I also want to keep it as easy and as simple as possible.

Simplicity is not easy, and it requires a lot of extra work. My goal is defined by these famous quotations:

"Make things as simple as possible, but not simpler." - Albert Einstein

"Perfection is achieved when there is nothing more to remove." - Saint-Exupery

"I feel very strongly that deep and simple is far more essential than shallow and complex." - Fred Rogers

http://www.youtube.com/watch?v=TMXKs6OSrNg

"Do the easiest thing that could possibly work, and then pound it into the simplest thing that could possibly work." - http://c2.com/cgi/wiki?SimplestOrEasiest (@archive.org)

EDIT: If you are wondering why I call my work-in-progress "touchpaint 2.0", here is "touchpaint-1.3":

https://www.mobileread.com/forums/sho...d.php?t=170932

[kaminkatze]

Originally Posted by geekmaster

"Normal" shell arrays did not work for me, but substrings work.

echo ${v:1:1} returns -sh: syntax error: Bad substitution on my K3, and expr substr $v 1 1 is even slower than hexdump.

Here is a ev[ia]l array style version.
eval "v=\$A${x}x$y".

I used 4 values. 0/1 for dead 100/101 for living. 1 and 101 are the dirty states wich are rendered with filled circles.

Spoiler:

#!/bin/sh

#=================================
# initvar - initialize global vars
#---------------------------------
initvar() {
  W=15 H=20; MX=$((W-1)) MY=$((H-1)); G=19 R=5
  LL=300; DLL=$((2*LL))
  for y in $(seq 0 $MY); do for x in $(seq 0 $MX); do
    eval "N${x}x$y=0"
  done; done
  DZ=/dev/zero DN=/dev/null DF=/dev/fb0
  B=$(echo -ne '\xff'); B=$B$B$B$B$B$B$B$B$B$B
  B=$B$B$B$B$B$B$B$B$B$B; B=$B$B$B$B$B$B$B$B$B$B
  eips -c
}

#============================
# load - load common patterns
# usage: load name
#----------------------------
load() {
  case $1 in
    glider) N1x0=101 N2x1=101 N0x2=101 N1x2=101 N2x2=101 ;;
    fill) for y in $(seq 0 $MY); do for x in $(seq 0 $MX); do
            eval "N${x}x$y=101"
          done; done;;
    spaceship) N1x0=101 N2x0=101 N3x0=101 N4x0=101 N4x1=101
               N4x2=101 N3x3=101 N0x1=101 N0x3=101 ;;
  esac
}

#==========================================
# circle - filled midpoint circle algorithm
# usage: echo $B | circle cx cy r
#        circle cx cy r <$DZ
#------------------------------------------
circle() {
  local cx=$1 cy=$2 r=$3; local e=$((-r)) x=$r y=0
  local x0 x1 x2 y0 y1 y2
  while [[ $x -ge $y ]]; do
    x0=$(((cy-x)*DLL+cx)) x1=$(((cy+x)*DLL+cx)) x2=$((2*x))
    y0=$(((cy-y)*DLL+cx)) y1=$(((cy+y)*DLL+cx)) y2=$((2*y))
    dd of=$DF bs=1 count=$x2 seek=$((y1-x))
    dd of=$DF bs=1 count=$x2 seek=$((y1+LL-x))
    dd of=$DF bs=1 count=$x2 seek=$((y0-x))
    dd of=$DF bs=1 count=$x2 seek=$((y0+LL-x))
    dd of=$DF bs=1 count=$y2 seek=$((x1-y))
    dd of=$DF bs=1 count=$y2 seek=$((x1+LL-y))
    dd of=$DF bs=1 count=$y2 seek=$((x0-y))
    dd of=$DF bs=1 count=$y2 seek=$((x0+LL-y))
    e=$((e+2*y+1)); y=$((y+1))
    if [[ $e -ge 0 ]]; then e=$((e-2*x-1)); x=$((x-1)); fi
  done 2>$DN
}

#======================
# update - update field
#----------------------
update() {
  for y in $(seq 0 $MY); do for x in $(seq 0 $MX); do
    eval "c=\$((\$L$(((x+MX)%W))x$(((y+MY)%H))\
               +\$L${x}x$(((y+MY)%H))\
               +\$L$(((x+1)%W))x$(((y+MY)%H))\
               +\$L$(((x+MX)%W))x$y\
               +\$L$(((x+1)%W))x$y\
               +\$L$(((x+MX)%W))x$(((y+1)%H))\
               +\$L${x}x$(((y+1)%H))\
               +\$L$(((x+1)%W))x$(((y+1)%H))))
          v=\$L${x}x$y
          if [[ \$v -lt 2 ]]; then
            [[ \$c -gt 299 -a \$c -lt 400 ]] && v=101 || v=0
          else
            [[ \$c -lt 200 -o \$c -gt 399 ]] && v=1 || v=100
          fi
          N${x}x$y=\$v"
  done; done
}

#=====================================
# render - copy current state and draw
#-------------------------------------
render() {
  for y in $(seq 0 $MY); do for x in $(seq 0 $MX); do
    eval "v=\$N${x}x$y; L${x}x$y=\$v"
    case $v in
      101) echo $B | circle $((x*G+G)) $((y*G+G)) $R ;;
      1) circle $((x*G+G)) $((y*G+G)) $R <$DZ ;;
    esac
  done; done; eips ''
}

#==========================
# loop - render update loop
#--------------------------
loop() { while true; do render; update; done; }

initvar
load glider
loop

[geekmaster]

Originally Posted by kaminkatze

echo ${v:1:1} returns -sh: syntax error: Bad substitution on my K3, and expr substr $v 1 1 is even slower than hexdump.

Hmm... I test most of my stuff on K4 and Touch. Only recently have I started trying scripting stuff on the K3 (due to the interest in this thread). I just now tested the ${a:b:c} type substrings on the K3, and the fail as you showed. I just tested again and they work on the Touch. If I want to support K3, I will have to use some more primitive constructs for the K3, instead of things like substring processing.

At least dd and hexdump work on everything...

I guess to be cross-platform, we need to find something that works on all of them. But for speed on newer kindles we also need newer things. Maybe we just need different scripts for different kindles...

For the K3, I guess it's back to $(echo $a|cut -b...)...

Calling commands that are built into busybox is not as time-consuming as one would think, because while running in /bin/sh, busybox is already memory-resident along with all its built-in commands. Other busybox commands may well be faster than advanced shell features partially or completely missing from the stripped-down busybox shell.

[geekmaster]

I have more complex event processing logic now that handles every possible condition (including "reserved" events), and I am very certain now that the swapped coordinates when you rotate across a 90-degree boundary is caused by a firmware bug. There is nothing more that I can do in my event processing except ignore the "slot" assignment events (that tell which finger the coordinates belong to) and just assign them to the last known finger position that was the closest to the four possible positions when swapping the new X or Y coordinate between finger positions.

This workaround should work fine as long as the distance between fingers is greater than the distance between sample points on a pair of fast-moving fingers. It would be a problem if the values near each other got swapped, but luckily, it is the OTHER coordinate that gets swapped, so this should be a reliable workaround.

All I did by rewriting my event handling logic was to become absolutely convinced that it is a firmware bug, even though I cannot find it in the GPL source code (yet)...

P.S. I am even handling the touchscreen "relative coordinate" mode (i.e. "mouse" mode) events now, so when I figure out how to switch the driver to relative mode (it looks like it uses a /proc for that), then we can let the driver do it instead of simulating it at the application level.

[kaminkatze]

Originally Posted by geekmaster

Part of the reason for doing this in /bin/sh is to get people involved who may not be ready for a compiled language, and to prove that we CAN do more than we think even with very primitive tools.

I feel like I'm not ready for a cross-compiled language (besides I never really used C).

This is how far I got (with the eips calls, thus same update speed) .

Run it with gameoflife savegame.png
The image is loaded via eips -g. The topmost row and leftmost column indicate the field position.