mirroring bits

Battle Bunny · January 2014

If I have a string of 1408 bytes, each of which has one bit 'b' set, what's the shortest way of mirroring that string, so that each bit set at position 'b' gets moved to position '7-b'? The bit positions change from byte to byte, as they're plots on a curve.

jamorski · January 2014

Something like this, though this doesn't work as it messes up when testing the end of the string address.

ld hl,$stringstart
	ld de,$stringend
lp	push hl
	ld a,(hl)
        ld b,$08
lp0     rra
        rl (hl)
        djnz lp0
	inc hl
	sbc hl,de
	jr c,lp
	ret

Dr BEEP · January 2014

jamorski wrote: »
Something like this, though this doesn't work as it messes up when testing the end of the string address.
ld hl,$stringstart
    ld de,$stringend
lp    push hl
    ld a,(hl)
        ld b,$08
lp0     rra
        rl (hl)
        djnz lp0
    inc hl
    sbc hl,de
    jr c,lp
    ret

POP HL?

jamorski · January 2014

No idea, eating a banana and trying to code is too much for my small intellect! :smile:

Ralf · January 2014

Instead of doing RRA in a loop the fastest way would be to use a mirror table which is a 8 bytes big as I understand so no problem with memory

Put the table on equal page start (C=0)

LD HL,DataStart
LD BC,TableStart
LD DE,1408

Loop
LD C,(HL)
LD A,(BC)
LD (HL),A
INC HL

DEC DE
LA A,D
OR E
JR Z,Loop

The loop counter could be probably optimized too.

Einar Saukas · January 2014

There are several ways to do it, depending on how much you care about performance or size.

Here's a solution using unrolled loop:

ld hl,$stringstart
	ld bc,$bytes
loop:	
        ld a,(hl)
REPT 8
        rra
        rl e
ENDR
        ld (hl),e
        cpi
        jp pe,loop
	ret

And another solution using a 256-aligned lookup table for mirroring:

ld hl,$stringstart
	ld bc,$bytes
        ld d,$lookuptable/256
loop:
        ld e,(hl)
        ld a,(de)
        ld (hl),a
        cpi
        jp pe,loop
	ret

Ralf · January 2014

This CPI as loop control is a nice thing. I'll add it to my tricks :)

Hikaru · January 2014

Building upon some of the above ideas, (namely Jamorski and Einar Saukas's)

InPlace
	ld hl,StringAddress
	ld bc,StringLength
.lp0
	ld a,#01
.lp1
	rr (hl)
	rla
	jr nc,.lp1
	ld (hl),a
	cpi
	jp pe,.lp0
	ret

Tabled
        ld h,high MirrorTable
        ld de,StringAddress
	ld bc,StringLength
.loop
        ld a,(de)
	ld l,a
        ldi
        jp pe,.loop
	ret

And also my own silly variation just for the sake of it :) 8 byte table at any address and maybe a bit faster than InPlace

WhyNotHaveBoth
	ld de,StringAddress
	ld bc,StringLength
.lp0
	ld hl,MirrorTable-1
	ld a,(de)
.lp1
	inc hl
	add a
	jr nc,.lp1
	ldi
	jp pe,.lp0
	ret

As an aside, the jump condition is 'parity even'.

Einar Saukas · January 2014

Hikaru wrote: »

Tabled
        ld h,high MirrorTable
        ld de,StringAddress
	ld bc,StringLength
.loop
        ld a,(de)
	ld l,a
        ldi
        jp pe,.lp0
	ret

Brilliant!

Hikaru wrote: »

And also my own silly variation just for the sake of it :) 8 byte table at any address and maybe a bit faster than InPlace

That's probably slower than my unrolled loop version on average, but if you use a 8-aligned table instead, it will work better...

Hikaru wrote: »

As an aside, the jump condition is 'parity even'.

I just edited my post above to fix it, thanks!

antoniovillena · January 2014

Not tested. An awkward way to do. It's fast but probably not the fastest one.

loop    ld      a, (hl)
        add     a, a
        jp      c, is80
        jp      m, is40
        cp      $08<<1
        jr      c, less08
        jp      z, write  ; $08->$10
        add     a, a
        jp      m, is20
is10    srl     (hl)      ; $10->$08
        jp      next
less08  cp      $02<<1
        ld      a, $40
        jp      z, write  ; $02->$40
        jr      c, is01
is04    rrca              ; $04->$20
        jp      write
is01    rrc     (hl)      ; $01->$80
        jp      next
is80    rlc     (hl)      ; $80->$01
        jp      next
is40    ld      a, $02    ; $40->$02
        defb    $f2       ; jp p, xxxx
is20    ld      a, $04    ; $20->$04
write   ld      (hl), a
next    inc     hl
        djnz    loop

Hikaru · January 2014

This just sorta came up all of a sudden.

InPlaceV2
	ld hl,StringAddress
	ld bc,StringLength
	scf
.loop
	rr (hl)
	jr nc,.loop
	cpi
	jp pe,.loop
	ret

Einar Saukas · January 2014

Hikaru wrote: »
This just sorta came up all of a sudden.
InPlaceV2
	ld hl,StringAddress
	ld bc,StringLength
	scf
.loop
	rr (hl)
	jr nc,.loop
	cpi
	jp pe,.loop
	ret

Nice :)

antoniovillena · January 2014

Hikaru wrote: »
This just sorta came up all of a sudden.
InPlaceV2
	ld hl,StringAddress
	ld bc,StringLength
	scf
.loop
	rr (hl)
	jr nc,.loop
	cpi
	jp pe,.loop
	ret

Wow. You are God.

Kweepa · January 2014

That is ingenious!
I came up with a way to reduce the size of the lookup table, if I understand the DAA instruction correctly.

Tabled
        ld h,high MirrorTable
        ld de,StringAddress
	ld bc,StringLength
loop:
        ld a,(de)  ; 1,2,4,8,10,20,40,80
        cpl          ; -> fe,fd,fb,f7,ef,df,bf,7f
        add a,0
        daa         ; -> 64,63,61,57,55,45,25,85
        srl a         ; -> 32,31,30,2b,2a,22,12,42
        sub 12h   ; -> 20,1f,1e,19,18,10,0,30 (49 bytes)
	ld l,a
        ldi
        jp pe,loop
	ret

Time: 7+4+7+4+8+7+4+16+10=67 per character.

I couldn't find any other cheap manipulations of the data that would reduce the range further, although no doubt they exist :)

Battle Bunny · January 2014

Hikaru wrote: »

This just sorta came up all of a sudden.

I don't think that can be improved upon. Thanks.

antoniovillena · January 2014

Kweepa wrote: »

I came up with a way to reduce the size of the lookup table

You can reduce the table from 128 bytes to 13 bytes with something like this:

        ld      h, high MirrorTable
        ld      de, StringAddress
        ld      bc, StringLength
        jr      lp0
lp1     rrca
        rrca
        rrca
        rrca
        add     5
        ld      l, a
        ldi
        ret     po
lp0     ld      a, (de)
        cp      $09
        jr      nc, lp1
        ld      l, a
        ldi
        jp      pe, lp0
        ret

Dr BEEP · January 2014

antoniovillena wrote: »

Wow. You are God.

Hikaru wrote: »
This just sorta came up all of a sudden.
InPlaceV2
	ld hl,StringAddress
	ld bc,StringLength
	scf
.loop
	rr (hl)
	jr nc,.loop
	cpi
	jp pe,.loop
	ret

Just a quick look:
Where is here the mirroring for i.e. 10101111?

antoniovillena · January 2014

Dr BEEP wrote: »

Just a quick look:
Where is here the mirroring for i.e. 10101111?

There is a restriction in the input, one 1 bit and seven 0 bits, so only 8 of 256 values are legal ($01, $02, $04, $08, $10, $20, $40, $80).

Dr BEEP · January 2014

antoniovillena wrote: »

There is a restriction in the input, one 1 bit and seven 0 bits, so only 8 of 256 values are legal ($01, $02, $04, $08, $10, $20, $40, $80).

Ok, didn't know that!

Paradigm Shifter · January 2014

You can use an 8 or 16 byte lookup and mirror each half of the byte separately. (16 possibilities for a 4bit half-byte, you can pack 2 into each byte for an 8 byte table, 16 bytes otherwise).

Kweepa · January 2014

That's what AntonioVillena's code above (with the 13 byte interleaved lookup table) is doing, or trying to do.

I wrote another version of it before realizing:

MirrorTable:
defb 0,80h,40h,0,20h,0,8,4,10h,2,0,0,0,1

ld h,high MirrorTable
ld de,StringAddress
ld bc,StringLength

loop:

; 7+7+7+4+16+10 = 55
ld a,(de)
and 0fh
jr z,upper
ld l,a
ldi
jp pe,loop

; (7+7+12)+7+4+4+4+4+7+7+4+16+10 = 93
upper:
ld a,(de)
rrca
rrca
rrca
rrca
and 0fh
add a,5
ld l,a
ldi
jp pe,loop

; avg. 74 cycles per loop + 14 byte interleaved table

By comparison, Hikaru's solution is about 143 cycles per loop. The OP was asking for the "shortest" answer, so this is just an alternative that balances speed and size for future reference.

mirroring bits

Comments