topic Re: division 32 bit by 16 bit in 8-bit Microcontrollers

division 32 bit by 16 bit

edjiang — Wed, 30 Jan 2013 15:16:50 GMT

Hi,

Does anyone has the assembly code for dividing 32 bit by 16 bit, i.e., unsigned long x, unsigned int?

in Freescale intrinsic_math.asm, there is only 32 bit by 8 bit division, as follows.

Thanks

;/*****************************************************************************

;* Module: unsigned int udiv32i8to16(unsigned long x, unsigned char y)

;* Description:

;* Unsigned integer dividing 32 bit by 8 bit from 16 bit Uword.

;* The Result is saturated at 0xFFFF if overflow occures.

;* Returns: x/y

;* Returns: Out3:Out2:Out1:Out0 = (x3:x2:x1:x0)/(y0) = x/y

;* Arguments: y (in) L1->5,SP; L2->6,SP;

;* H1->3,SP; H2->4,SP;

;* y (in) A

;* Range Issues: None

;* Special Issues: HCS08S -Cs08 Option backend. The result is saturated

;*****************************************************************************/

udiv32i8to16:

PSHA ;

TAX ; y -> X

TST 4,SP ;

BNE udiv32Sat

LDA 5, SP

PSHA

PULH

LDA 6, SP

DIV ;

BCS udiv32Sat

PSHA

LDA 8, SP

DIV

TAX ;z0 -> X

PULH ;z1 -> H

PULA

RTS

udiv32Sat:

LDHX #0FFFFh

PULA

RTS

Re: division 32 bit by 16 bit

Encoder1 — Wed, 30 Jan 2013 18:12:46 GMT

Hi Ed,

This is a solution. The routine uses some zero-page ram for Quotient, Divisor and Result (2x 4byte) and some bytes more (3) from stack. It is all noted.

; variables declaration (IntAcc1 & IntAcc2)

Quotient:

Remainder:

IntAcc1: ; 4-bytes integer accum. #1

TEMP1 ds 1

TEMP2 ds 1

Dividend:

TEMP3 ds 1

TEMP4 ds 1

Divisor:

IntAcc2: ; 4-bytes integer accum. #2

TEMP5 ds 1

TEMP6 ds 1

TEMP7 ds 1

TEMP8 ds 1

;**************************************************

; 32 x 16 UNSIGNED DIVIDE

;

; This routine takes the 32-bit dividend stored in

; IntAcc1:IntAcc1+3 and divides it by the 16-bit

; divisor stored in IntAcc2:IntAcc2+1.

; The quotient replaces the dividend and the

; remainder replaces the divisor.

; Time length: 1720us @ 2MHz BusClock with call

;**************************************************

UDVD32 pshh ; save H-reg value

psha ; save accumulator

pshx ; save H-reg value

ais #-3 ; reserve three bytes of

; temp storage

lda #32

sta 3,SP ; loop cntr for nr. shifts

lda Divisor ; get divisor Msb

sta 1,SP ; put divisor Msb in

; working storage

lda Divisor+1 ; get divisor lsb

sta 2,SP ; put divisor lsb in

; working storage

; Shift all four bytes of dividend 16 bits to the

; right and clear both bytes of the temporary

; remainder location

mov Dividend+1,Dividend+3 ; shift divid. lsb

mov Dividend,Dividend+2 ; shift 2nd byte

; of dividend

mov Dividend-1,Dividend+1 ; shift 3rd byte

; of dividend

mov Dividend-2,Dividend ; shift divid. Msb

clr Remainder ; zero remain. Msb

clr Remainder+1 ; zero remain. lsb

; Shift each byte of dividend and remainder one bit

; to the left

ShftLP lda Remainder ;get remainder Msb

rola ;shift remainder Msb into

;carry

rol Dividend+3 ;shift dividend lsb

rol Dividend+2 ;shift 2nd byte of dividend

rol Dividend+1 ;shift 3rd byte of dividend

rol Dividend ;shift dividend Msb

rol Remainder+1 ;shift remainder lsb

rol Remainder ;shift remainder Msb

; Subtract both bytes of the divisor from remainder

lda Remainder+1 ;get remainder lsb

sub 2,SP ;subtract divisor lsb from

;remainder lsb

sta Remainder+1 ;store new remainder lsb

lda Remainder ;get remainder Msb

sbc 1,SP ;subtract divisor Msb from

;remainder msb

sta Remainder ;store new remainder Msb

lda Dividend+3 ;get low byte of

;dividend/quotient

sbc #0 ;dividend low bit holds

;subtract carry

sta Dividend+3 ;store low byte of

;dividend/quotient

; Check dividend/quotient lsb. If clear, set lsb of

; quotient to indicate successful subraction, else

; add both bytes of divisor back to remainder

brclr 0,Dividend+3,SetLsb ;check for a carry

;from subtraction and add

;divisor to remainder if set

lda Remainder+1 ;get remainder lsb

add 2,SP ;add divisor lsb to

;remainder lsb

sta Remainder+1 ;store remainder lsb

lda Remainder ;get remainder Msb

adc 1,SP ;add divisor Msb to

;remainder Msb

sta Remainder ;store remainder msb

lda Dividend+3 ;get low byte of dividend

adc #0 ;add carry to low bit of

;dividend

sta Dividend+3 ;store low byte of dividend

bra Decrmt ;do next shift and subtract

SetLsb bset 0,Dividend+3 ;set lsb of quotient to

;indicate successive

; subtraction

Decrmt dbnz 3,SP,ShftLP ;decrement loop counter and

;do next shift

; Move 32-bit dividend into IntAcc1:IntAcc1+3 and put

; 16-bit remainder in IntAcc2:IntAcc2+1

lda Remainder ;get remainder msb

sta 1,SP ;temporarily store

;remainder msb

lda Remainder+1 ;get remainder lsb

sta 2,SP ;temporarily store rem.r lsb

mov Dividend,Quotient

mov Dividend+1,Quotient+1 ;shift all four

;bytes of quotient

mov Dividend+2,Quotient+2 ;16 bits to the

;left

mov Dividend+3,Quotient+3

lda 1,SP ;get final remainder Msb

sta IntAcc2 ;store final remainder Msb

lda 2,SP ;get final remainder lsb

sta IntAcc2+1 ;store final remainder lsb

; Deallocate local storage, restore register values,

; and return from subroutine

ais #3 ;deallocate temporary storage

pulx ;restore X-reg value

pula ;restore accumulator value

pulh ;restore X-reg value

rts

Sorry the editor on the forum made a mess with the original formatting, but it is a minor problem: copy it on a good word editor with fixed character size (courier new). The routine is fully tested and I use it in my programs in assembler. Anyway the original text is attached in asm format.

Good luck,

Salvatore

Re: division 32 bit by 16 bit

eckhard — Wed, 30 Jan 2013 23:17:58 GMT

Hello,

here is an old Appnote for the HC08 with a 32 Bit by 16 Bit Division.

http://cache.freescale.com/files/microcontrollers/doc/app_note/AN1219.pdf?fsrch=1&WT_TYPE=Application%20Notes&WT_VENDOR=…

Regards Eckhard

Re: division 32 bit by 16 bit

edjiang — Thu, 31 Jan 2013 09:36:33 GMT

Hi Salvatore,

Thanks for sharing the code. I have a question: how can I apply your code? for example, I used it in a way as follows, but it didn't work.

Thanks

//////////////////////////////////////////////////////////////////////////////

void UDVD32(unsigned long x, unsigned int y);

//////////////////////////////////////////////////////////////////////////////

signed long *sumS32;

unsigned int *counterU8;

signed int outTemp;

UDVD32(*sumS32, *counterU8);

outTemp = -(signed int)*sumS32;

Re: division 32 bit by 16 bit

Encoder1 — Thu, 31 Jan 2013 22:17:20 GMT

I am sorry Ed,

I am not able to fully understand your C code: I never studied it and use only assembler. Obviously there is no problem to use my assembler routine if correctly called by a C code, but i am not able to say how! I hope someone else can do.

The routine works perfectly in assembler when you fill "IntAcc1" 4 byte long buffer with the Dividend and "IntAcc2" 2 byte long buffer with the Divisor, then call UDVD32. The result will override the divisor (quotient) in IntAcc1 buffer and the remainder will override the divisor in IntAcc2. To work both IntAcc1 and IntAcc2 must reside on page zero.

Please note that my routine was taken and updated from AN1219 cited by Eckhard as it is internally written on, so they are essentially the same.

Salvatore

Re: division 32 bit by 16 bit

bigmac — Fri, 01 Feb 2013 01:41:01 GMT

Hello Ed,

Ed Jiang wrote:

Thanks for sharing the code. I have a question: how can I apply your code? for example, I used it in a way as follows, but it didn't work.

//////////////////////////////////////////////////////////////////////////////

void UDVD32(unsigned long x, unsigned int y);

//////////////////////////////////////////////////////////////////////////////

signed long *sumS32;

unsigned int *counterU8;

signed int outTemp;

UDVD32(*sumS32, *counterU8);

outTemp = -(signed int)*sumS32;

Your request seems a little confused! The original post seemed to require an assembly sub-routine for the division process - with code duly provided by Encoder. However, your later post does imply that you actually require a C function for the same process.

The attached code provides a suite of arithmetic functions, that includes a 64-bit by 32-bit unsigned division function. The functions actually make use of HLI assembly code within each function to optimise speed.

Of course, it is possible to adapt the C function as a "pure" assembly sub-routine. I have attempted to do this within the second attachment. This code snippet is untested - errors are quite possible. As with the C functions, the ASM sub-routine makes use of the stack for intermediate data storage, and does not require use of additional memory within zero-page RAM.

All functions and the sub-routine assume unsigned division process. If you are working with signed quantities, you will need to separately determine the sign of the resulting quotient, and then convert the dividend and divisor to positive values (and cast to unsigned), prior to calling the function.

Regards,

Mac

Re: division 32 bit by 16 bit

edjiang — Fri, 01 Feb 2013 14:57:51 GMT

Hi Mac,

Thanks for your reply. What I am looking for is the algorithm which can perform the division and can be called easily in C code. I am doing an averaging to a signal collected by ADC module. I only concern about the quotient, in other words, I need only the quotient and skip the remainder. Therefore, it would be perfect if there is a return of the quotient value when the sub-routine (or C function) is call, for example Quotient_average = UDVD32(*sumS32, counterU8Loc);

I modified my code in order to call the algorithm provided by Salvatore.

#pragma DATA_SEG SHORT MY_ZEROPAGE

unsigned long IntAcc1;

unsigned int IntAcc2;

unsigned int Quotient_average;

.........

unsigned long *sumS32;

unsigned int *counterU8;

IntAcc1 = *sumS32;

IntAcc2 = *counterU8;

UDVD32;

Quotient_average = (unsigned int)IntAcc1;

In the meantime, I compare the quotient value with the result using another algorithm 32 bit divided by 8 bit. This value should be more constant because it is an average of more samples, but it isn't. Therefore, I am sure the division of 32 bit by 16 bit still fails. Can you give me a hint how I should modified my code?

Regards,

Re: division 32 bit by 16 bit

bigmac — Sun, 03 Feb 2013 06:52:26 GMT

Hello Ed,

For the division process associated with calculating an arithmetic average, you probably do not need to handle a 16-bit divisor (unless you are averaging more than 255 samples). A 32 by 8 bit division process will suffice in most cases. This function will execute significantly faster since the DIV instruction can be utilised within a "long division" process.

However, I would be aiming to make the number of samples to be averaged an exact power of two. In this case, the division process simply involves a right shift of the data.

With 256 samples, the division process is trivial. Simply ignore the LS byte, and read the next 16 bits. This may be accommodated using a union between the 32-bit dividend, and a structure containing the 16-bit result.

Regards,

Mac

Re: division 32 bit by 16 bit

edjiang — Mon, 04 Feb 2013 09:39:19 GMT

Hi Mac,

That is a very good idea! I will make the sampling a power of two times. By the way, I inserted the C-function you provided, and it works pretty well.

Thanks a lot to you and others (Salvatore and Eckhard) who replied to my question!

Have a nice day!

Re: division 32 bit by 16 bit

KEC — Mon, 18 Mar 2013 16:25:11 GMT

Mac,

I greatly appreciate the Math32.zip source code.

I used several of the functions with expected results except for "word TBLINTPL( word *table, byte tabndx, byte intplfrac);". Was it intended for "tabndx" to specify the second of the pair of values to be used. I expect "tabndx" to specify the first (e.g. table[0]). I only get the behavior I expect if I delete the "AIX #-2 // Point to entry_1 data" instruction.

Thanks again for the many helpful posts,

Kevin

Re: division 32 bit by 16 bit

bigmac — Wed, 20 Mar 2013 06:56:49 GMT

Hello Kevin,

KEC wrote:

I used several of the functions with expected results except for "word TBLINTPL( word *table, byte tabndx, byte intplfrac);". Was it intended for "tabndx" to specify the second of the pair of values to be used. I expect "tabndx" to specify the first (e.g. table[0]). I only get the behavior I expect if I delete the "AIX #-2 // Point to entry_1 data" instruction.

The value of tabndx was intended to reference the first table value. The present code for this funtion contains a previously undiscovered bug. I agree with your solution to the problem.

Regards,

Mac