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

Go To Last Post
25 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

adreading/255=x/23, solve for x

 

Imagecraft compiler user

Last Edited: Thu. Sep 22, 2016 - 12:14 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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....

 

 

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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
 adc r24,r25
 ror r24
 adc r24,r25
 ror r24
 lsr r24
 adc r24,r25
 ror r24
 andi r24,0xf0
 swap r24

add:

+ 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
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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()
{
  int val = analogRead(0);
  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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

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"!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

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
add	r24, r0
adc	r25, r1
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 frown

Last Edited: Fri. Sep 23, 2016 - 10:12 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

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 ) 

 

add

again add 1 so it take 14 clk.

Last Edited: Fri. Sep 23, 2016 - 11:06 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I looked at your code, of course, but the algorithm I posted in #5 calls for a mul, so I coded a mul.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

As long the mul is with a const it should be simple, but only used at -O3 etc, because the code get's big (it's smaller (and slower) to call a lib).