Recherche avancée

Sur d’autres sites (7932)

• Revisiting the Belco Alpha-400

  26 août 2010, par Multimedia Mike — General

  Relieved of the primary FATE maintenance duties, I decided to dust off my MIPS-based Belco Alpha-400 and try to get it doing FATE cycles. And just as I was about to get FATE running, I saw that Mans already got his MIPS-based Popcorn Hour device to run FATE. But here are my notes anyway.

  
  
  

  Getting A Prompt
  For my own benefit, I made a PDF to remind me precisely how to get a root prompt on the Alpha-400. The ‘jailbreak’ expression seems a little juvenile to me, but it seems to be in vogue right now.

  alpha-400-jailbreak.pdf

  Toolchain
  When I last tinkered with the Alpha-400, I was trying to build a toolchain that could build binaries to run on the unit’s MIPS chip, to no avail. Sometime last year, MichaelK put together x86_32-hosted toolchains that are able to build mipsel 32-bit binaries for Linux 2.4 and 2.6. The Alpha-400 uses a 2.4 kernel and the corresponding toolchain works famously for building current FFmpeg (--disable-devices is necessary for building).

  FATE Samples
  Next problem : Making the FATE suite available to the Alpha-400. I copied all of the FATE suite samples onto a VFAT-formatted SD card. The filename case is not preserved for all files which confounds me since it is preserved in other cases. I tried formatting the card for ext3 but the Alpha-400 would not mount it, even though /proc/filesystems lists ext3 (supporting an older version of ext3 ?).

  Alternative : Copy all of the FATE samples to the device’s rootfs. Space will be a little tight, though. Then again, there is over 600 MB of space free ; I misread earlier and thought there were only 300 MB free.

  Remote Execution
  To perform FATE cycles on a remote device, it helps to be able to SSH into that remote device. I don’t even want to know how complicated it would be to build OpenSSH for the device. However, the last time I brought up this topic, I learned about a lighter weight SSH replacement called Dropbear. It turns out that Dropbear runs great on this MIPS computer.

  Running FATE Remotely
  I thought all the pieces would be in place to run FATE at this point. However, there is one more issue : Running FATE on a remote system requires that the host and the target are sharing a filesystem somehow. My personal favorite remote filesystem method is sshfs which is supposed to work wherever there is an SSH server. That’s not entirely true, though– sshfs also requires sftp-server to be installed on the server side, a program that Dropbear does not currently provide.

  I’m not even going to think about getting Samba or NFS server software installed on the Alpha-400. According to the unit’s /proc/filesystems file, nfs is a supported filesystem. I hate setting up NFS but may see if I can get that working anyway.

  Residual Weirdness
  The unit comes with the venerable Busybox program (BusyBox v1.4.1 (2007-06-01 20:37:18 CST) multi-call binary) for most of its standard command line utilities. I noticed a quirk where BusyBox’s md5sum gives weird hex characters. This might be a known/fixed issue.

  Another item is that the Alpha-400′s /dev/null file only has rwxr-xr-x per default. This caused trouble when I first tried to scp using Dropbear using a newly-created, unprivileged user.

• Of ctors and dtors

  18 février 2011, par Multimedia Mike — Programming, Sega Dreamcast

  I haven’t given up on the Sega Dreamcast programming. I was able to compile a bunch of homebrew code for the DC many years ago and I can’t make it work anymore. Again, I was working with a purpose-built, open source RTOS named KallistiOS (or KOS). I can make the programs compile but not run. I had ELF files left over from years ago which still executed. But when I tried to build new ELF files, no luck— the programs crashed before even reaching my main() function.

  I found the problem : ELF files are comprised of a number of sections and 2 of these sections are named ’.ctors’ and ’.dtors’ which stand for constructors and destructors. The KOS RTOS performs a manual traversal of .ctors section during program initialization and this is where things go bad. The traversal code doesn’t seem to account for a .ctors section that only contains a single entry. I commented out the function that does the traversal and programs started to work, at least until it was time to exit the program and return control to the program loader. That’s when the counterpart .dtors section traversal code ran and demonstrated the same problem. I’ll exhibit the problematic code at the end of this post.

  So I’m finally tinkering with Sega Dreamcast programming once again and with a slightly better grasp of software engineering than the first time I did this.

  Portable and Compatible C ?
  If nothing else, this low-level embedded stuff exposes you to some serious toolchain arcana, the likes of which you will likely never see working strictly in the desktop arena.

  Still, this exercise makes me wonder why C code from a decade ago doesn’t compile reliably now. Part of it is because gcc has gotten stricter about the syntax it will accept. In the case of this specific crashing problem, I suspect it comes down to a difference in the way the linker generates the final ELF file. I’ve written a list of items I have had to modify in the KOS codebase in order to get it to compile on more recent gcc versions. I wonder if it would be worth publishing the specifics, or if anyone would ever find the information useful ? Oh, who am I kidding ? Of course I’ll write it up, perhaps publish a new version of the code, if only because that’s the best chance I have of finding my own work again some years down the road.

  Problematic C Code
  See if this code makes any sense to you. It somehow traverse a list of 32-bit function pointers (in different directions, depending on constructors or destructors), executing each in turn. However, it appears to fall over if the list of pointers consists of a single entry.
  

  PLAIN TEXT

  C :

  1. typedef void (*fptr)(void) ;
  2.  
  3. static fptr ctor_list[1] __attribute__((section(".ctors"))) = { (fptr) -1 } ;
  4. static fptr dtor_list[1] __attribute__((section(".dtors"))) = { (fptr) -1 } ;
  5.  
  6. /* Call this to execute all ctors */
  7. void arch_ctors() {
  8.     fptr *fpp ;
  9.  
  10.     /* Run up to the end of the list (defined by crtend) */
  11.     for (fpp=ctor_list + 1 ; *fpp != 0 ; ++fpp)
  12.          ;
  13.  
  14.     /* Now run the ctors backwards */
  15.     while (—fpp> ctor_list)
  16.         (**fpp)() ;
  17. }
  18.  
  19. /* Call this to execute all dtors */
  20. void arch_dtors() {
  21.     fptr *fpp ;
  22.  
  23.     /* Do the dtors forwards */
  24.     for (fpp=dtor_list + 1 ; *fpp != 0 ; ++fpp )
  25.         (**fpp)() ;
  26. }

• Basic Video Palette Conversion

  20 août 2011, par Multimedia Mike — General, Python

  How do you take a 24-bit RGB image and convert it to an 8-bit paletted image for the purpose of compression using a codec that requires 8-bit input images ? Seems simple enough and that’s what I’m tackling in this post.

  Ask FFmpeg/Libav To Do It
  Ideally, FFmpeg / Libav should be able to handle this automatically. Indeed, FFmpeg used to be able to, at least at the time I wrote this post about ZMBV and was unhappy with FFmpeg’s default results. Somewhere along the line, FFmpeg and Libav lost the ability to do this. I suspect it got removed during some swscale refactoring.

  Still, there’s no telling if the old system would have computed palettes correctly for QuickTime files.

  Distance Approach
  When I started writing my SMC video encoder, I needed to convert RGB (from PNG files) to PAL8 colorspace. The path of least resistance was to match the pixels in the input image to the default 256-color palette that QuickTime assumes (and is hardcoded into FFmpeg/Libav).

  How to perform the matching ? Find the palette entry that is closest to a given input pixel, where "closest" is the minimum distance as computed by the usual distance formula (square root of the sum of the squares of the diffs of all the components).

  
  
  

  That means for each pixel in an image, check the pixel against 256 palette entries (early termination is possible if an acceptable threshold is met). As you might imagine, this can be a bit time-consuming. I wondered about a faster approach...

  Lookup Table
  I think this is the approach that FFmpeg used to use, but I went and derived it for myself after studying the default QuickTime palette table. There’s a pattern there— all of the RGB entries are comprised of combinations of 6 values — 0x00, 0x33, 0x66, 0x99, 0xCC, and 0xFF. If you mix and match these for red, green, and blue values, you come up with 6 * 6 * 6 = 216 different colors. This happens to be identical to the web-safe color palette.

  The first (0th) entry in the table is (FF, FF, FF), followed by (FF, FF, CC), (FF, FF, 99), and on down to (FF, FF, 00) when the green component gets knocked down and step and the next color is (FF, CC, FF). The first 36 palette entries in the table all have a red component of 0xFF. Thus, if an input RGB pixel has a red color closest to 0xFF, it must map to one of those first 36 entries.

  I created a table which maps indices 0..215 to values from 5..0. Each of the R, G, and B components of an input pixel are used to index into this table and derive 3 indices ri, gi, and bi. Finally, the index into the palette table is given by :

    index = ri * 36 + gi * 6 + bi
  

  For example, the pixel (0xFE, 0xFE, 0x01) would yield ri, gi, and bi values of 0, 0, and 5. Therefore :

    index = 0 * 36 + 0 * 6 + 5
  

  The palette index is 5, which maps to color (0xFF, 0xFF, 0x00).

  Validation
  So I was pretty pleased with myself for coming up with that. Now, ideally, swapping out one algorithm for another in my SMC encoder should yield identical results. That wasn’t the case, initially.

  One problem is that the regulation QuickTime palette actually has 40 more entries above and beyond the typical 216-entry color cube (rounding out the grand total of 256 colors). Thus, using the distance approach with the full default table provides for a little more accuracy.

  However, there still seems to be a problem. Let’s check our old standby, the Big Buck Bunny logo image :

  
  
  Distance approach using the full 256-color QuickTime default palette
  
  
  Distance approach using the 216-color palette
  
  
  Table lookup approach using the 216-color palette
  

  I can’t quite account for that big red splotch there. That’s the most notable difference between images 1 and 2 and the only visible difference between images 2 and 3.

  To prove to myself that the distance approach is equivalent to the table approach, I wrote a Python script to iterate through all possible RGB combinations and verify the equivalence. If you’re not up on your base 2 math, that’s 2²⁴ or 16,777,216 colors to run through. I used Python’s multiprocessing module to great effect and really maximized a Core i7 CPU with 8 hardware threads.

  So I’m confident that the palette conversion techniques are sound. The red spot is probably attributable to a bug in my WIP SMC encoder.

  Source Code
  Update August 23, 2011 : Here’s the Python code I used for proving equivalence between the 2 approaches. In terms of leveraging multiple CPUs, it’s possibly the best program I have written to date.

  PLAIN TEXT

  PYTHON :

  1. # !/usr/bin/python
  2.  
  3. from multiprocessing import Pool
  4.  
  5. palette = []
  6. pal8_table = []
  7.  
  8. def process_r(r) :
  9.  counts = []
  10.  
  11.  for i in xrange(216) :
  12.   counts.append(0)
  13.  
  14.  print "r = %d" % (r)
  15.  for g in xrange(256) :
  16.   for b in xrange(256) :
  17.    min_dsqrd = 0xFFFFFFFF
  18.    best_index = 0
  19.    for i in xrange(len(palette)) :
  20.     dr = palette[i][0] - r
  21.     dg = palette[i][1] - g
  22.     db = palette[i][2] - b
  23.     dsqrd = dr * dr + dg * dg + db * db
  24.     if dsqrd <min_dsqrd :
  25.      min_dsqrd = dsqrd
  26.      best_index = i
  27.    counts[best_index] += 1
  28.  
  29.    # check if the distance approach deviates from the table-based approach
  30.    i = best_index
  31.    r = palette[i][0]
  32.    g = palette[i][1]
  33.    b = palette[i][2]
  34.    ri = pal8_table[r]
  35.    gi = pal8_table[g]
  36.    bi = pal8_table[b]
  37.    table_index = ri * 36 + gi * 6 + bi ;
  38.    if table_index != best_index :
  39.     print "(0x%02X 0x%02X 0x%02X) : distance index = %d, table index = %d" % (r, g, b, best_index, table_index)
  40.  
  41.  return counts
  42.  
  43. if __name__ == ’__main__’ :
  44.  counts = []
  45.  for i in xrange(216) :
  46.   counts.append(0)
  47.  
  48.  # initialize reference palette
  49.  color_steps = [ 0xFF, 0xCC, 0x99, 0x66, 0x33, 0x00 ]
  50.  for r in color_steps :
  51.   for g in color_steps :
  52.    for b in color_steps :
  53.     palette.append([r, g, b])
  54.  
  55.  # initialize palette conversion table
  56.  for i in range(0, 26) :
  57.   pal8_table.append(5)
  58.  for i in range(26, 77) :
  59.   pal8_table.append(4)
  60.  for i in range(77, 128) :
  61.   pal8_table.append(3)
  62.  for i in range(128, 179) :
  63.   pal8_table.append(2)
  64.  for i in range(179, 230) :
  65.   pal8_table.append(1)
  66.  for i in range(230, 256) :
  67.   pal8_table.append(0)
  68.  
  69.  # create a pool of worker threads and break up the overall job
  70.  pool = Pool()
  71.  it = pool.imap_unordered(process_r, range(256))
  72.  try :
  73.   while 1 :
  74.    partial_counts = it.next()
  75.    for i in xrange(216) :
  76.     counts[i] += partial_counts[i]
  77.  except StopIteration :
  78.   pass
  79.  
  80.  print "index, count, red, green, blue"
  81.  for i in xrange(len(counts)) :
  82.   print "%d, %d, %d, %d, %d" % (i, counts[i], palette[i][0], palette[i][1], palette[i][2])