Is there a logical algorithm to generate unique outputs for the given inputs?

user_16345447 0
Viewed 71

I have a table of inputs that needs to output a unique formatted byte. The bytes outputted from the algorithm need to have only 1 bit on, giving 8 unique outputs. The inputs do not have to correlate with a specific output as long as each input has a unique output. The following is a list of all possible inputs and outputs.

Inputs: -00001000 -00001001 -00000001 -00000101 -00000100 -00000110 -00000010 -00001010

Outputs: -10000000 -01000000 -00100000 -00010000 -00001000 -00000100 -00000010 -00000001

I would like to know if there is a logical algorithm which is designed to do this. I'm currently using a lookup table for this which is not very optimized. I have access to all the operations used in 6502 assembly.

I've given my lookup table code as one possible solution in an answer, but I'm looking for something better if it exists.

6502 assembly
3 Answers

18 bytes, 11 cycles

A small lookup table will be the smallest, fastest and don't forget most versatile solution to your question. You can easily change how these numbers map to each other.

LDX input     ;  2 bytes, 3 cycles (Zero Page)
LDA lookup,X  ;  3 bytes, 5 cycles
STA output    ;  2 bytes, 3 cycles (Zero Page)

lookup:       ; 11 bytes
  .byte $00,$20,$02,$00,$08,$10,$04,$00,$80,$40,$01

Tip: Perhaps the first byte ($00) of the lookup table could double up as the terminating zero of some string that you need in your program anyway. That's one trick I've used more than once over the years.

18 bytes, 10 cycles

Shave off 1 cycle by making absolutely sure that the lookup table does not cross a page boundary (5 cycles then becomes 4 cycles).

LDX input     ;  2 bytes, 3 cycles (Zero Page)
LDA lookup,X  ;  3 bytes, 4 cycles
STA output    ;  2 bytes, 3 cycles (Zero Page)

lookup:       ; 11 bytes
  .byte $00,$20,$02,$00,$08,$10,$04,$00,$80,$40,$01

17 bytes, 10 cycles

Shave off 1 byte and 1 cycle by placing the lookup table on the zero page (3 bytes then becomes 2 bytes).

LDX input     ;  2 bytes, 3 cycles (Zero Page)
LDA lookup,X  ;  2 bytes, 4 cycles (Zero Page)
STA output    ;  2 bytes, 3 cycles (Zero Page)

lookup:       ; 11 bytes
  .byte $00,$20,$02,$00,$08,$10,$04,$00,$80,$40,$01
user_31447700

I don't know the details of 6502, so this could or could not be efficient than a lookup table approach.

out = 1 << (in == 8 ? 7 : in & 7 ^ (in & 8) >> 2)

It has the following mapping for your given inputs.

in -> out (hex)
 8 -> 80
 9 -> 8
 1 -> 2
 5 -> 20
 4 -> 10
 6 -> 40
 2 -> 4
 a -> 1

The formula came out by scribbling random things on a paper, so not much logic.

Test

user_176658070

Unfortunately, I do not think there is a more efficient method than a lookup table.

This is the code for my lookup table. It uses 18 bytes and 11 clock cycles. The obvious flaw is that you are wasting 2 of the bytes in the lookup table and that the lookup table itself uses 11 bytes.

LDX input     ;Zero Page
LDA lookup,X
STA output    ;Zero Page
lookup:
  .byte $00,$20,$02,$00,$08,$10,$04,$80,$40,$01
user_163454470
Related