Re: Quilted Dies of CPU & RAM

On Tue, 14 Nov 2006 17:33:09 +0100, Dave Long wrote:
> >> In an industry that only clocks progress on linear semi-log plots
> >> true innovation has become rare -- it's far too risky at the high
> >> end.
> >
> > Right --- it's the anti-Innovator's-Dilemma.  As long as focusing on
> > making stuff smaller can get you 50+% improvements every year, you'll
> > beat all the Teras and Symbolicses just by doing that.
> 
> In DSP-land (the last refuge of VLIW?) strange innovations can find a  
> home.
> 
> A couple of years ago* I'd wondered about gray-coded PC increments.   
> Well, the DSP people haven't gone that far, but they do offer the  
> option of bit-reversed autoincrementing index registers.  By counting  
> left-to-right (x000, x100, x010, x110, x001, x101, x011, x111, x000...)  
> one can get various power-of-two circular buffers "for free".
> 
> That may seem like a lot of trouble to save a mask op, but there's a  
> good market reason to provide the feature: bit reversal simplifies  
> twiddling FFT butterflies.

Interesting.  Ward Cunningham is currently using bit-reversed counters
in his Bynase code for PDM [0] --- he's doing the equivalent of a
fixed dither pattern in the time domain rather than just doing the
delta-sigma thing.

My current best approaches to this in software are

  unsigned char spec_binc(unsigned char acc) {
    unsigned char mask;
    for (mask = 0x80; mask & acc; mask >>= 1) 
      acc ^= mask; 
    return mask | acc;
  }

which is 5 AVR instructions in the inner loop, so probably 6 cycles;
12 instructions in all; average case should be around 18 cycles, worst
case around 50; and

  unsigned char table16[] = { 0x08, 0x09, 0x0a, 0x0b,  0x0c, 0x0d, 0x0e, 0x0f,
                              0x04, 0x05, 0x06, 0x07,  0x02, 0x03, 0x01, 0x00 };

  unsigned char table16_reverse_counter(unsigned char input) {
    unsigned char lefthalf = input >> 4;
    unsigned char nextleft = table16[lefthalf];
    unsigned char righthalf = input & 0x0f;
    unsigned char nextright = (nextleft ? righthalf : table16[righthalf]);
    return ((unsigned char)(nextleft << 4) | nextright);
  }

which I think can be better both in the average case and the worst
case if you avoid doing address arithmetic by aligning table16 on a
256-byte boundary, but is better only in the worst case as output by
gcc.

Again we get back to the missing perfect-shuffle instruction [1]
--- reversing the bits in a byte requires only three perfect
in-shuffles:

  abcd EFGH
  EaFb GcHd
  GEca HFdb
  HGFE dcba

[0] http://c2.com/cybords/wiki.cgi?BynaseProtocol

[1] http://lists.canonical.org/pipermail/kragen-tol/2006-February/000814.html