## if-else vs. array look-up for different number base

25 posts / 0 new
Author
Message

Im trying to take an 8 bit value from the ADC of an ATTINY48 and convert it into a number between 1 and 23 - I suppose you could say I was converting the number into a number of base 23. Im looking for the fastest way of doing this - im not very experienced with embedded stuff - I have tried using repeated if - else statements - which is slow - and containing all 256 different possible outcomes in an array - which uses up all my memory. What is the best / fastest way of doing this? Might it be an algorithm to sort the number into a base 23 number? Or is there something easier i have missed?

Imagecraft compiler user

Last Edited: Thu. Sep 22, 2016 - 12:14 PM

As Bob says isn't it just something like:

`N = (ADC / 11.13) + 1`

where 11.13 = 256 / 23.

The +1 just moves 0..22 to 1..23

And if you need speed make a 256 LUT (placed in flash).

You can follow these steps (you can check with an hex calculator):

ADC input: 0x??, multiply by 22 to get:

0xMMRR, where MM is 0-21 and RR is the remainder. Add 0x0100 to get:

0xNNRR, where NN is 1-22 and RR is the remainder. If you want decimals, take the low byte 0xRR (remainder) and multiply by 10 to get:

0x0KSS, where K is 0-9 and SS is the next remainder.

And that's it.

OK! thanks, I forgot to just use arithmetic

sparrow2 wrote:

And if you need speed make a 256 LUT (placed in flash).

how do I put things in flash? I assume that's different from just declaring an array at the start of the program - as in "const char ADCvals[256] = {0,0,0.....};" ?

If I start dividing a char by a non integer, does this cause problems? I've not done arithmetic before with avr....

pgo480 wrote:
as in "const char ADCvals[256] = {0,0,0.....};" ?

It depends on which C compiler you use. If it is avr-gcc the syntax (in the modern compiler, that is 4.6 or later) is:

`const __flash char ADCvals[256] = {0,0,0.....};`

Other compilers have their own equivalent of "__flash".

pgo480 wrote:
If I start dividing a char by a non integer, does this cause problems?
It will include the float library. Again if you use avr-gcc the lib is libm.a and the basic floating point arithmetic (+/-*) will "cost" 700 bytes for a CPU that has MUL. In other compilers it can cost up to about 3K.

In a 4K micro I don't know if 0.7K can be considered "significant" or not? As El Tangas showed, integer scaling is a possibility if you cannot afford the cost of float.

Last Edited: Thu. Sep 22, 2016 - 12:57 PM

ok that's good to know but i think ill go with storing a look up  table in flahs, that sounds quickest...

im pretty sure that i am using the avr-gcc compiler but declaring

`const __flash char ADCvals[256] = {0,0,0.....};`

doesn't seem to work, also using PROGMEM doesn't seem to work either. Is there anything else I need to include for this to work?

Now, I'm just an old bit-pusher that likes to do things simply.

AVR8's have a 10-bit ADC.  In practice with real-world signals, it is often hard to get right down to zero counts, or be exact at the high end.

So many of my transfer functions for e.g. external 0-5VDC control signal from pot or whatever will toss out the low 10 counts and call anything below that 0.  The toss everything over 1010 and call that "top"  The remaining 1000 counts are then used to get 0.0% to 100.0% in whatever units.

Why am I rambling?  Tell more about this 1-23 number.  Really 0-23, so now base 24?  Toss some counts at the low end divide the remaining counts by 40, and limit the highest result to 23.

clawson wrote:
where 11.13 = 256 / 23.

Tiny48, eh?  We have that in a couple apps, but don't use it widely due to the wimpy pin drive.  And in the end it is still a Tiny.  [AVR8 prices are jumpy after the new overlords took over but] for a little bit more the Mega48 gives you more stuff and an easy upgrade path.

Anyway, "Tiny".  Do you really want to drag in floating point?  The obvious divisor is 1113/100.  89/8 is good to 2 decimal places.  56/5 is good to one decimal place and doesn't require extending to 32 bits for the intermediate result.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

the number should be 0-22, base 23. I've just rejected the lower numbers and read them as an 8 bit... but i think the easiest / quickest way is to store a lookup table in the flash memory, no?

Yeah, you may be right about the attiny48 being wimpy, but the job it's doing is so simple there's not really any need to go up to a mega48 - if i can store this in the flash ill be fine.....   plus, here and now, i have an attiny48 and don't have an atmega48

Are you really planning to fill 256 bytes with this?...

```1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,
2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,
3,3,4,4,4,4,4,4,4,4,4,4,4,5,5,5,
5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,
6,6,6,7,7,7,7,7,7,7,7,7,7,7,8,8,
8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,
9,9,9,9,9,10,10,10,10,10,10,10,10,
10,10,10,11,11,11,11,11,11,11,11,
11,11,11,12,12,12,12,12,12,12,12,
12,12,12,13,13,13,13,13,13,13,13,
13,13,13,14,14,14,14,14,14,14,14,
14,14,14,15,15,15,15,15,15,15,15,
15,15,15,16,16,16,16,16,16,16,16,
16,16,16,16,17,17,17,17,17,17,17,
17,17,17,17,18,18,18,18,18,18,18,
18,18,18,18,19,19,19,19,19,19,19,
19,19,19,19,20,20,20,20,20,20,20,
20,20,20,20,21,21,21,21,21,21,21,
21,21,21,21,22,22,22,22,22,22,22,
22,22,22,22,23,23,23,23,23,23,23,
23,23,23,23```

Perhaps it is "quick" but it just seems like such a waste of space.

BTW I generated that with:

```\$ cat test7.c
#include <stdio.h>

int main(void) {
int i;
for (i = 0; i < 256; i++) {
printf("%d,", (int)(i / 11.13) + 1);
}
return 0;
}
\$ gcc test7.c -o test7
\$ ./test7
```

yes that's right. it only took me a few minutes to type it - it's not the end of the world

It's more of a philosophical point I suppose, but I would say it's not a waste of space if there's otherwise going to be no useful information in it.

- of course, if there is a faster method of doing it then i'll use that. I'd like speed, I have space to burn

- not that im not interested in the other methods, it's all good to know...

I still like #5. In the simplest form I guess you are looking at:

`N1to23 = ((ADC * 23) + 0x100) >> 8;`

to test that:

```\$ cat test7.c
#include <stdio.h>

int main(void) {
int i, Nint, Nfloat;
for (i = 0; i < 256; i++) {
Nint = ((i * 23) + 0x100) >> 8;
Nfloat = (int)(i / 11.13) + 1;
if (Nint != Nfloat) {
printf("breaks at %d, Nint=%d, Nfloat=%d\n", i, Nint, Nfloat);
break;
}
printf("%d,", Nfloat);
}
return 0;
}
```

That does not print the "break at" message when run.

Built for AVR the code is:

```    N1to23 = ((ADCH * 23) + 0x100) >> 8;
76:	95 b1       	in	r25, 0x05	; 5
78:	87 e1       	ldi	r24, 0x17	; 23
7a:	98 9f       	mul	r25, r24
7c:	c0 01       	movw	r24, r0
7e:	11 24       	eor	r1, r1
80:	80 50       	subi	r24, 0x00	; 0
82:	9f 4f       	sbci	r25, 0xFF	; 255
84:	89 2f       	mov	r24, r25
86:	99 0f       	add	r25, r25
88:	99 0b       	sbc	r25, r25
8a:	9a 83       	std	Y+2, r25	; 0x02
8c:	89 83       	std	Y+1, r24	; 0x01```

Last Edited: Thu. Sep 22, 2016 - 02:43 PM

And if you wish you can add 0x0180 instead of 0x0100 to round to nearest instead of truncate.

Edit: taking a closer look at that compiler output, it seems the compiler is generating some extra code to track the sign of the ints, my guess is using uint16_t variables may give smaller code.

Last Edited: Thu. Sep 22, 2016 - 04:21 PM

yes, #5 is neat, ill try that one too

but cliff (#14) op use a tiny (your code use mul!).

I don't know if a compiler can make something close but this asm code do the job (input r24 output r24, r25 change)

``` mov r25,r24
lsr r24
lsr r24
lsr r24
ror r24
ror r24
lsr r24
ror r24
andi r24,0xf0
swap r24
```

+ inc r24

and the code do 89/2048 so it's correct for all 8 bit numbers.

Last Edited: Thu. Sep 22, 2016 - 08:58 PM

I like the Arduino Map() function for that:  works with C or C++!

/* Map an analog value to 8 bits (0 to 23) */
void setup() {}

void loop()
{
val = map(val, 0, 1023, 0, 23);
analogWrite(9, val);
}

For the mathematically inclined, here's the whole function

```long map(long x, long in_min, long in_max, long out_min, long out_max)
{
return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
}

```

The fastest way is to digitize into the range 0...23, or 0..46 and right shift, or 0...92, and right shift 2, or 0...184 and right shift three.  Do you have control over the signal or reference? 10 turn pots with a resistor on each end to select the range can be *very* precise.

Looks like there is a trade off between software speed, size, and readability/trickiness. Usually, smaller ram and rom computers are cheaper. Adding hardware like bigger ram and rom or external peripherals adds expense. The way capitalists make money is to make a product that competes on price and features. Depending on the number of units (10? 100? 1000? 10K? 100K?) eliminating a 5 cent diode could save \$5000 on parts. If you can do a 'software diode' and spread the extra software effort over the production run, it might pay off. I think this sort of tradeoff expense spreadsheet is the realm of system engineering rather than software engineering. Rare Birds those dudes that know about whats expensive and whats simple in software and in hardware. The software validation of a flight control computer for an airliner is a Big Deal. The software validation of a voting machine that might tilt the election of a person that could alter the course of human history is also a Big Deal. This is the realm of Software Engineering. You need an ISO 9100 auditor to validate your software quality process. Also a Big Deal. The flight control computer needs to be validated by a DO178 Designated Engineering Representative. Yet Another Big Deal.

Imagecraft compiler user

sparrow2 wrote:
but cliff (#14) op use a tiny (your code use mul!).
Oops, missed the "tiny" fact. In that case, building for tiny48 gives:

```    N1to23 = ((ADCH * 23) + 0x100) >> 8;
44:	80 91 79 00 	lds	r24, 0x0079
48:	90 e0       	ldi	r25, 0x00	; 0
4a:	67 e1       	ldi	r22, 0x17	; 23
4c:	70 e0       	ldi	r23, 0x00	; 0
4e:	08 d0       	rcall	.+16     	; 0x60 <__mulhi3>
50:	80 50       	subi	r24, 0x00	; 0
52:	9f 4f       	sbci	r25, 0xFF	; 255
54:	89 2f       	mov	r24, r25
56:	99 0f       	add	r25, r25
58:	99 0b       	sbc	r25, r25
5a:	9a 83       	std	Y+2, r25	; 0x02
5c:	89 83       	std	Y+1, r24	; 0x01
5e:	ff cf       	rjmp	.-2      	; 0x5e <__SREG__+0x1f>

00000060 <__mulhi3>:
60:	55 27       	eor	r21, r21
62:	00 24       	eor	r0, r0

00000064 <__mulhi3_loop>:
64:	80 ff       	sbrs	r24, 0
66:	02 c0       	rjmp	.+4      	; 0x6c <__mulhi3_skip1>
68:	06 0e       	add	r0, r22
6a:	57 1f       	adc	r21, r23

0000006c <__mulhi3_skip1>:
6c:	66 0f       	add	r22, r22
6e:	77 1f       	adc	r23, r23
70:	61 15       	cp	r22, r1
72:	71 05       	cpc	r23, r1
74:	21 f0       	breq	.+8      	; 0x7e <__mulhi3_exit>
76:	96 95       	lsr	r25
78:	87 95       	ror	r24
7a:	00 97       	sbiw	r24, 0x00	; 0
7c:	99 f7       	brne	.-26     	; 0x64 <__mulhi3_loop>

0000007e <__mulhi3_exit>:
7e:	95 2f       	mov	r25, r21
80:	80 2d       	mov	r24, r0
82:	08 95       	ret
```

Agree that is not "great"!

The poor compiler is limited to use generic multiply code. It can't generate a specialized code that does only "multiply by 23", for example this code simulates the result of a "mul" instruction:

```;mul r24 by 23, result in r24:r25
;assumes r1 = 0
mov	r0, r24
lsl	r24
mov	r25, r1
rol	r25
lsl	r24
rol	r25
lsl	r24
rol	r25
lsl	r24
rol	r25
sub	r24, r0
sbc	r25, r1```

Actual calculation is ((2*N + N) * 8 - N). The day a compiler can generate stuff like this, I'll start to be really worried about the future of mankind

Last Edited: Fri. Sep 23, 2016 - 10:12 AM

But why mul with 23, it's divide with 23 we need?

Look at #17 that is a mul with 89/2048= 1/(23,011) and is correct for all 8 bit nubers.

It take 13 clk, and only change r24 and r25 so it's easy to implement (close to the speed of a LUT after you have pushed and pulled )