English Amiga Board


Go Back   English Amiga Board > Coders > Coders. General

 
 
Thread Tools
Old 08 August 2006, 17:47   #1
alexh
Thalion Webshrine
alexh's Avatar
 
Join Date: Jan 2004
Location: Oxford
Posts: 12,218
Help coding

Is there a simple way to Mirror data?

My input data sets are very confined, they are just "one-hot". Meaning that only 1-bit can be set at once.

Code:
0001 ($1) = 1000 ($8)
0010 ($2) = 0100 ($4)
0100 ($4) = 0010 ($2)
1000 ($8) = 0001 ($1)
I actually need to Mirror then invert

Code:
0001 ($1) = 0111 ($7)
0010 ($2) = 1011 ($B)
0100 ($4) = 1101 ($D)
1000 ($8) = 1110 ($E)
If there isnt a simple arithmetical technique I'll just implement a switch statement in ASM.

I have the usual MOVE, NOT, AND, XOR, OR, SL, SR opcodes etc.

Last edited by alexh; 09 August 2006 at 15:12.
alexh is offline  
Old 08 August 2006, 23:03   #2
Npl
Registered User
 
Join Date: Aug 2004
Location: Vienna / Austria
Age: 40
Posts: 257
Im pretty sure they aint an easy way. I`d use a 256-entry table with inverted bytes.
Npl is offline  
Old 08 August 2006, 23:17   #3
Codetapper
2 contact me: email only!

Codetapper's Avatar
 
Join Date: May 2001
Location: Auckland / New Zealand
Posts: 3,158
I'm not sure what you mean by one hot, do you mean they are always one bit set? If that is the case, you can get around the table problem, as you know which bit is set so can mirror it by setting the mirrored bit straight away then doing the not operation on it.

But if that isn't the case, a 256 byte table that you generate is probably the best way to go, and you can fill in the mirrored not'd version at the same time meaning a byte lookup will be very quick.
Codetapper is offline  
Old 09 August 2006, 02:45   #4
girv
Registered User

girv's Avatar
 
Join Date: Aug 2004
Location: Northern Ireland
Posts: 923
I remember asking this question years ago on csa.games I think. I wanted to reverse the order of bits in a byte or word. The best anyone came up with was a lookup table, just like the others have said already.

Also, avoid the switch statement approach if performance is important.
girv is offline  
Old 09 August 2006, 15:03   #5
alexh
Thalion Webshrine
alexh's Avatar
 
Join Date: Jan 2004
Location: Oxford
Posts: 12,218
Quote:
Originally Posted by Codetapper
I'm not sure what you mean by one hot, do you mean they are always one bit set?
Oops. Sorry for not explaining. One-Hot (in this case) means that only one bit can be set at once. Think of each bit as being a mutually exclusive flag.

Quote:
If that is the case, you can get around the table problem, as you know which bit is set so can mirror it by setting the mirrored bit straight away then doing the not operation on it.
The data is an input, an interrupt status register. You dont know which of the four bits is set. It could be any of them.

Quote:
But if that isn't the case, a 256 byte table that you generate is probably the best way to go
Because it is "one-hot" it's effectively just a 4-entry lookup table. But I dont have any memory (other than instruction memory) so I cannot implement a true lookup table.

But I was hoping there was a simple arithmetic operation so that I wouldnt have to do any SUBI+BCC instructions.

Last edited by alexh; 09 August 2006 at 15:42.
alexh is offline  
Old 09 August 2006, 15:54   #6
girv
Registered User

girv's Avatar
 
Join Date: Aug 2004
Location: Northern Ireland
Posts: 923
Quote:
Originally Posted by alexh
The data is an input, an interrupt status register. You dont know which of the four bits is set. It could be any of them.

Because it is "one-hot" it's effectively just a 4-entry lookup table. But I dont have any memory (other than instruction memory) so I cannot implement a true lookup table.

But I was hoping there was a simple arithmetic operation so that I wouldnt have to do any SUBI+BCC instructions.
In your case you'd need only a 9 byte lookup table, using the 4 bits of input information as an index into a byte table holding the output value you need. Can't you spare 9 bytes? It would probably take more in instruction bytes to code an algorithm to do the same job!

If you're on 020-040 you could look at the BFFFO (Bit Field Find First One) instruction. IIRC it exists on 060 as well but is emulated.

I don't know the exact syntax of BFFFO but your code would be something like this.

Code:
; > d0.l = input status value

bfffo  d0{0:31},d1 ; d1 = bit position of first 1 bit
neg.b  d1    ; get d1 = 3-d1
addq.b #3,d1
moveq  #0,d0 ; set only bit d1 in d0
bset   d1,d0
not.b  d0    ; invert d0 to get final value
I now sit back and wait for the Obvious Mistake Police to pounce.
girv is offline  
Old 09 August 2006, 16:00   #7
Galahad/FLT
Going nowhere

Galahad/FLT's Avatar
 
Join Date: Oct 2001
Location: United Kingdom
Age: 46
Posts: 7,302
What machine is this for where memory is so critical?
Galahad/FLT is offline  
Old 09 August 2006, 16:36   #8
alexh
Thalion Webshrine
alexh's Avatar
 
Join Date: Jan 2004
Location: Oxford
Posts: 12,218
It's a PicoController inside a hardware RAID5 controller that I designed (using the 68k instructions as a template)

It has no RAM at all. Just 16*48-bit registers and a 512 entry instruction RAM.

One of the team want to do something it wasnt supposed to do and is looking for a workaround using the minimum number of instructions and the minimum number of cycles.

Had I known they would ever have wanted to do anything like this I would have added it to the load instruction.

It would have added little more than 4 x 2:1 mux's and 4 wires (i.e. nothing!)
alexh is offline  
Old 09 August 2006, 18:29   #9
Photon
Moderator

Photon's Avatar
 
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,733
For this example, you can do it without bit mirroring, by looking at the values:

Code:
Flip:	;d0=4-bit input
	addq.b #6,d0
	cmp.b #7,d0
	beq.s .done
	cmp.b #14,d0
	beq.s .done
	addq.b #3,d0
.done:	rts
Photon is offline  
Old 09 August 2006, 19:05   #10
alexh
Thalion Webshrine
alexh's Avatar
 
Join Date: Jan 2004
Location: Oxford
Posts: 12,218
Top man.
alexh is offline  
Old 09 August 2006, 21:22   #11
Npl
Registered User
 
Join Date: Aug 2004
Location: Vienna / Austria
Age: 40
Posts: 257
You could use x = 0x8 / x. but thats likely not supported or slow

If a variable shift is availabe, you could use a special bitmask v = 111100010000 and shift that to the right v=v>>x, then add x>>2 to the result x = x>>2+v. The low 4 bits contain the mirrored pattern.

Im not fluent at m68k assembly, I added some C-style remarks to make it clear

Code:
Flip:	;d0=4-bit input
	move #F10, d1	;d1 = 0xF10
	lsr.w d0,d1	; d1 = (d1 >> d0)
	lsr.b #2, d0	; d0 = (d0>>2)
	add d1,d0	; d0 = d0 + d1
	andi.b #7, d0	; d0 = d0&0x7
	rts
Photons code of course will do the same, but I consider avoiding branches an art
Dunno which one would be faster/smaller on m68k
Npl is offline  
Old 09 August 2006, 21:31   #12
Psygore
Moderator

Psygore's Avatar
 
Join Date: Jan 2002
Location: France
Posts: 484
Here a 4bit mirroring:
Code:
input : d0
output : d1

roxr.b #1,d0
addx.b d1,d1
roxr.b #1,d0
addx.b d1,d1
roxr.b #1,d0
addx.b d1,d1
roxr.b #1,d0
addx.b d1,d1
not.b d1           ;invert value
and.b #%1111,d1
Psygore is offline  
Old 11 August 2006, 00:37   #13
AGN
Registered User
 
Join Date: Aug 2004
Location: Poland
Posts: 142
Optimized Photon version:

Code:
d0 - input
d1 - output

        add.b   #6,d0
        move.l  d0,d1
        and.b   #4,d0
        bne     done
        add.b   #3,d1
done:
only 4 and a half instruction - did I fit in cycles?

ps.
send more puzzles like this one ;)
AGN is offline  
Old 14 August 2006, 01:40   #14
Photon
Moderator

Photon's Avatar
 
Join Date: Nov 2004
Location: Eksjö / Sweden
Posts: 4,733
Great! Or even:

Code:
	addq.b #6,d0
	btst #2,d0
	bne.s .done
	addq.b #3,d0
.done:
Photon is offline  
Old 15 August 2006, 09:24   #15
alexh
Thalion Webshrine
alexh's Avatar
 
Join Date: Jan 2004
Location: Oxford
Posts: 12,218
@AGN & Photon
Cool. I can do that.

I dont have the instruction BTST in my hardware but unlike the 68k I do have 3 operands in my instructions (src1, src2, dest)

Have to see which is faster. Avoiding branches is good in 99% of situations, but using delay slots can mean zero penalty in some situations. (This isnt a situation where you can use a delay slot on it's own but maybe the other code fits around it)

Last edited by alexh; 15 August 2006 at 09:29.
alexh is offline  
 


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
Any of you Coding on Amiga? Amiga Forever Coders. General 42 31 January 2012 02:58
Coding a bootblock Yesideez Coders. General 15 23 May 2010 00:13
What gives you coding inspiration? pmc Coders. General 55 16 November 2009 21:45
Need help with audio coding. Thorham Coders. General 6 05 March 2008 08:38
Coding with Devpac 3.18 Seoman Coders. General 8 08 November 2007 13:34

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 18:09.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.
Page generated in 0.08873 seconds with 13 queries