AVR Freaks

And I guess that I should add, that :

Because a NEG on 16 bit  only take 3 clk on an AVR signed should use same rutine.(negaiv either output direct '-' or remember and negate number).

Nice job

Have not checked all numbers but seems to be correct.

Yeah, I like to keep my options open. Maybe it's a macro, maybe it's inline, maybe add the entry point and ret and it's a function.

Truth is, I don't even know what are avr-gcc calling conventions, this is just an embodiment of the algorithm, the rest are details.

I've rewritten the code to be callable from C. It's a function (utobcd) that takes an uint16_t argument and returns the base 10 representation as an unpacked BCD in the lower 5 bytes of an uint64_t (the 3 high bytes are undefined). I think it will be much more useful like this, maybe eventually the thread objective will actually be reached

;             +--------------------------+
;             | uint16_t to 5 byte BCD   |
;             | by El Tangas @AVRFreaks  |
;             |          2016            |
;             +--------------------------+
;
; input: little endian uint16_t in R25:R24
; output: little endian unpacked BCD in R22:R21:R20:R19:R18
;         accessible from C as 5 lower bytes of an uint64_t
; changes: R18-R25 (the uint64_t output) and R0

.global utobcd
utobcd:
;needed constants - 16777.216 = 1/1000 * 256 * 65536
	ldi	r22, (16777)&0xFF	;Low
	ldi	r23, (16777)>>8		;High

;16x16 mul input * 16777 = (input/1000) << 24
	mul	r24, r22	;Low * Low
	movw	r18, r0
	mul	r25, r23	;High * High
	movw	r20, r0

	mul	r25, r22	;High * Low
	clr	r22		;zero register for arithmetic operations
	add	r19, r0
	adc	r20, r1
	adc	r21, r22

	mul	r24, r23	;Low * High
	add	r19, r0
	adc	r20, r1
	adc	r21, r22

;divide original value by 4 (only more significant byte is needed) and add
;in other words, add input * 0.25 to obtain a better aproximation (input * 16777.25)
	lsr	r25
	lsr	r25
	subi	r25, -2		;add 2 to correct rounding errors (need to always round up)
	add	r19, r25
	adc	r20, r22	;r20:r19 contains rounded remainder, r18 discarded
	adc	r21, r22	;r21 contains 10000s and 1000s (0-65)

;16x8 mul r20:r19 by 10
	ldi	r24, 10		;load constant 10
	mul	r19, r24
	movw	r18, r0
	mul	r20, r24
	add	r19, r0
	adc	r1, r22
	mov	r20, r1		;r20 contains 100s
	inc	r19		;r19 contains rounded remainder, r18 discarded

;8x8 mul r19 by 10
	mul	r19, r24	;multiply remainder by 10
	movw	r18, r0		;r19 contains 10s, r18 remainder

;8x8 mul r18 by 10
	mul	r18, r24	;multiply remainder by 10
	mov	r18, r1		;r18 contains units

;extract 2 high digits from r21 (does nothing if initial value is in 0-9999 range)
;this algo is only valid for 0-68 range due to sloppy correction but it's enough
;divide by 10 for first digit
	ldi	r25, 26		;load constant 26 = 1/10 * 256 rounded up
	mul	r21, r25	;equivalent to (div by 10) << 8
	mov	r22, r1
	sub	r0, r1		;correct the remaider (equivalent to multiply by 25.9)
;multiply remainder by 10 for second digit
	mul	r0, r24
	mov	r21, r1

	clr	r1		;restore zero_reg for avr-gcc compatibility
	ret

As an usage example, this is the test code I wrote to validate this function (Arduino code):

extern "C" uint64_t utobcd(uint16_t);

int main() {
	uint16_t counter = 0;
	uint64_t result;
 	do {
		result = utobcd(counter);
		if (((result & 0xFF00000000) >> 32) != (counter / 10000)) break;
		if (((result & 0xFF000000) >> 24) != ((counter % 10000) / 1000)) break;
		if (((result & 0xFF0000) >> 16) != ((counter % 1000) / 100)) break;
		if (((result & 0xFF00) >> 8) != ((counter % 100) / 10)) break;
		if ((result & 0xFF) != (counter % 10)) break;
		counter++;
	} while(counter != 0); //repeat until counter overflows

	//if test successful, light up LED
	if (counter == 0) {
		DDRB |= (1<<5);
		PORTB |= (1<<5);
	}
}

It compares the output of the utobcd function with equivalent calculations made in C, if successful lights the Arduino built in LED (or if first iteration fails - not gonna happen). Result: LED lights after ~4s.

edit: changed "5 lower bits" to "5 lower bytes" in code description (thanks for spotting this, Simonetta)

edit 2: initialized 'counter' to zero (thanks, theusch)

And that was why I wrote :

For the general code it should output with '0'-'9' with ST Y+,rnn, so it should output in correct order. (and then try to reuse reg. so the footprint get's small)

 

which output do we expect like 123 should output:

"123"

"00123"

"  123"

"123  "

And for signed where to add the '-'

or is that a pre and post job? 

I wonder if an optimized routine for selected bases could be written in C, and thus benefit from instructions only available on newer versions of the AVR8 architecture? I'm not sure there is anything really helpful in there, but a lot of the instruction timings are different on XMEGA for example, so... What is the baseline for cycle counting, MEGA AVRs?

There is also the question of unrolling loops and the like. Size vs. speed trade off. Seems like base 16 is going to be easy, maybe start there.

Why do humans write numbers backwards? If only we had had the foresight to write them little endian we could save a few cycles!

The problem is that many want log data in a readable format, and in those situations speed sometimes matter. 

I guess that you never have been out and made systems for the industry, they often insist on a csv format. (speed don't matter for the "main" but for the little AVR it does)

this is not for "loggers" but logging data, on a system that do something else. (often when you trim the system).

You can't expect that a none programmer out in the industry have to look at the temperature as F8 F9 FA ..... he want a human numbers, and with a terminal(program), can log the data, and show them in excel etc. (And that is the way he has done it the last 20+ years )    

I've added leading zero elimination and ASCII conversion to my routine, now it should be compatible with utoa, with hardcoded base 10.

;             +--------------------------+
;             |    uint16_t to ASCIIZ    |
;             | by El Tangas @AVRFreaks  |
;             |          2016            |
;             +--------------------------+
;
; input: little endian uint16_t in R25:R24
;        char* in R23:R22
; output: returns the input char*, that now points to an ASCIIZ string
;         containing a decimal representation of the input uint16_t
; changes: R18-R25 and R0

.global __utoa10
__utoa10:
	movw	r30, r22
;needed constants - 16777.216 = 1/1000 * 256 * 65536
	ldi	r22, (16777)&0xFF	;Low
	ldi	r23, (16777)>>8		;High

;16x16 mul input * 16777 = (input/1000) << 24
	mul	r24, r22	;Low * Low
	movw	r18, r0
	mul	r25, r23	;High * High
	movw	r20, r0

	mul	r25, r22	;High * Low
	clr	r22			;zero register for arthmetic operations
	add	r19, r0
	adc	r20, r1
	adc	r21, r22

	mul	r24, r23	;Low * High
	add	r19, r0
	adc	r20, r1
	adc	r21, r22

;divide original value by 4 (only more significant byte is needed) and add
;in other words, add input * 0.25 to obtain a better aproximation (input * 16777.25)
	lsr	r25
	lsr	r25
	subi	r25, -2		;add 2 to correct rounding errors (need to always round up)
	add	r19, r25
	adc	r20, r22	;r20:r19 contains rounded remainder, r18 discarded
	adc	r21, r22	;r21 contains 10000s and 1000s (0-65)

;16x8 mul r20:r19 by 10
	ldi	r24, 10		;load constant 10
	mul	r19, r24
	movw	r18, r0
	mul	r20, r24
	add	r19, r0
	adc	r1, r22
	mov	r20, r1		;r20 contains 100s
	inc	r19			;r19 contains rounded remainder, r18 discarded

;8x8 mul r19 by 10
	mul	r19, r24	;multiply remainder by 10
	movw	r18, r0		;r19 contains 10s, r18 remainder

;8x8 mul r18 by 10
	mul	r18, r24	;multiply remainder by 10
	mov	r18, r1		;r18 contains units

;extract 2 high digits from r21 (does nothing if initial value is in 0-9999 range)
;this algo is only valid for 0-68 range due to sloppy correction but it's enough
;divide by 10 for first digit
	ldi	r25, 26		;load constant 26 = 1/10 * 256 rounded up
	mul	r21, r25	;equivalent to (div by 10) << 8
	mov	r22, r1
	sub	r0, r1		;correct the remaider (equivalent to multiply by 25.9)
;multiply remainder by 10 for second digit
	mul	r0, r24
	mov	r21, r1

	clr	r1				;restore zero_reg for avr-gcc compatibility
	movw	r24, r30	;setup return char*
	ldi	r23, '0'	;constant for ASCII conversion

;leading zero elimination
	cpse	r22, r1		;skip 10000s digit if zero
	rjmp	digit_10000
	cpse	r21, r1		;skip thousands digit if zero
	rjmp	digit_1000
	cpse	r20, r1		;skip hundreds digit if zero
	rjmp	digit_100
	cpse	r19, r1		;skip tens digit if zero
	rjmp	digit_10
	rjmp	digit_1		;units cannot be skipped
;convert to ASCII and store string
digit_10000:
	add	r22, r23
	st	z+, r22
digit_1000:
	add	r21, r23
	st	z+, r21
digit_100:
	add	r20, r23
	st	z+, r20
digit_10:
	add	r19, r23
	st	z+, r19
digit_1:
	add	r18, r23
	st	z+, r18
;add \0 string terminator
	st	z, r1
	ret

The code size, 126 bytes, is now larger than the original utoa. Cycle count is 76/78/79/80/81 for 1-5 digits (including call and ret instructions).

Tested in Arduino with this code:

extern "C" char* __utoa10(uint16_t, char*);

int main() {
	uint16_t counter = 0;
	char result[6];
 	do {
		if (((uint16_t) atol(__utoa10(counter, result))) != counter) break;
		counter++;
	} while(counter != 0); //repeat until counter overflows

	//if test sucessful, light up LED
	if (counter == 0) {
		DDRB |= (1<<5);
		PORTB |= (1<<5);
	}
}

edit: initialized counter to zero.

I'm following these guidelines, so I expect the code to be "safe". According to these rules, I can change r18-r27, r30-r31 and r0. I can also use r1 but it must be restored to zero on exit.

Ok I had some time and here is a ASM version that can run on all AVR's (with RAM).

It is 78 byte, and take max 201 clk (76  200 if you have a defined zero reg.)

But the best is actually the small amount of registers used, only 2 other than input data and pointer

It don't print starting 0's so 123 is printed as 123\0

It's based on the count down up down ....

;input r17:r16
;input Z point to string start
;change r16,r17,r24,r25,Z 


        mov     r25,ZL      ;remember org pointer start
        ldi     r24, '0'-1
ML1:	inc     r24
        subi    r16, low(10000)       
        sbci    r17, high(10000)
        brcc    ML1
        cpi     r24,'0'
        breq    PL1         ;never print a 0 on first digit
        st      Z+,r24

PL1:
        ldi     r24, '0'+10
ML2:	dec     r24
        subi    r16, low(-1000)       
        sbci    r17, high(-1000)
        brcs    ML2
        cpi     r24,'0'
        brne    PL2         ;!= '0' print
        cpse	ZL,r25      ;if nothing printed don't print '0'
PL2:	st      Z+,r24


        ldi     r24, '0'-1
ML3:	inc     r24
        subi    r16, low(100)           
        sbci    r17, high(100)
        brcc    ML3
        cpi     r24,'0'
        brne    PL3         ;!= '0' print
        cpse    ZL,r25      ;if nothing printed don't print '0'
PL3:	st      Z+,r24


        ldi     r24, '0'+10
ML4:	dec     r24
        subi    r16, -10 
        brcs    ML4
        cpi     r24,'0'
        brne    PL4         ;!= '0' print
        cpse    ZL,r25      ;if nothing printed don't print '0'
PL4:	st      Z+,r24


        subi    r16, -'0'
        st      Z+,r16      ;always print last digit
        ldi     r16, 0
        st      Z+,r16      ;0 terminator

I will look at a faster version but the code will be bigger, but something like 150 byte and 120clk should be possible

An other way is something like a 40 byte 300 clk version

Last version before bed time it make both count down and up on each digit (but down with a factor 2 bigger).

It 68 byte and max 188 clk

_digit:
		ldi r24,'0'
_digit1:
		subi r24,-2
		sub r16,r18
		sbc r17,r19
		brcc _digit1
		lsr r19
		ror r18
		add r16,r18
		adc r17,r19
		brcs _digit3
		dec r24
		add r16,r18
		adc r17,r19
//		rjmp _digit4
_digit3:dec r24
_digit4:
		cpi		r24,'0'
		brne	_digit2			;!= '0' print
		cpse	ZL,r25		;if nothing printed don't print '0'
_digit2:st		Z+,r24
		ret

convert:
		mov		r25,ZL		;pointer have movet print digit
		ldi     r18,low(20000)
		ldi     r19,high(20000)
		rcall    _digit
		ldi     r18,low(2000)
		ldi     r19,high(2000)
		rcall    _digit
		ldi     r18,low(200)
		ldi     r19,high(200)
		rcall    _digit
		ldi     r18,low(20)
;		ldi     r19,high(20)
		rcall    _digit
        subi    r16, -'0'
		st		Z+,r16	;always print last digit
		st		Z+,r19	;terminator

I'm not an expert on inline asm, but isn't that just failing because you're telling avr-gcc you're clobbering r28, and avr-gcc requires r28 to be saved and restored? I.e. you can use it however you want if you think you know better, but telling the compiler what you're doing will make it angry.

I had a look at how small it can be, and I guess that the code like this is one of the smallest I can think of at the moment.

It is zero terminated, but the zeros aren't removed so 123 will print 00123\0 

It use a 16/8 div routine and because the digits come in the wrong order the zeros is a pain to remove!

it take r17:r16 as input and Z is the pointer

and it take about 760 clk

But it's only 38 byte in size. 

Any smaller code?

convert:
        ldi     r24,10           ;div with 10
	adiw	Z,5
	ldi	r23,5
con0:   clr     r18             ;reminder
        ldi     r25,0x10        ;loop 16 bit
con1:   lsl     r16
        rol     r17
        rol     r18
        cp      r18,r24
        brcs    con3
con2:   sub     r18,r24
        inc     r16
con3:   dec     r25
        brne    con1
	subi	r18,-'0'		;go to ACSII
	st	-Z,r18
        dec     r23
	brne    con0
	std	Z+5,r16			;0 terminating string

Edit forgot an init

But that is a good reason to use decimal numbers in you log.