Remainder

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

Hi I have searched this forum and many other places looking for an example of doing say (3 MOD 3) in assembly with is just modulo remainder and I am working with mega48.

What I want to do is say load r16 with 3, r17 with 3 and do the Math 'MOD' function on those numbers in assembly for avr and produce output to r18.

If anyone can help I would be forever greatful. It is probally very simple but I can not find an implementation.

Thanks

Last Edited: Thu. Jul 13, 2006 - 04:34 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

if the modulo is a power of two, it's simply a bitwise AND.with (modulo-1)
3 and 3 = 0 (mod 4)
4 and 3 = 1
17 and 15 = 1 (mod 16)
65535 and 255 = 255 (mod 256)

Otherwise, the general case is to divide and take the remainder

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

modulo can be from 2 - 256 so how would I divide and take the remainder?

Thanks for the quick response

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

the bits left over after ANDing with 0x07 are the remainder of the modulo 0x08 divide? 7 mod 4 is 3, so this works?

Imagecraft compiler user

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

Unless you're dealing with the special case of "modulo-powers-of-two-minus-one", the straight forward approach would be to implement full integer division, and look at the remainder instead of the quotient when you're all done.

Atmel has an application note available dealing with integer division/multiplication arithetic, including computing remainders, which may guide you through the process -- AVR200.

Last Edited: Tue. Jul 11, 2006 - 04:34 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Suggest you read:

http://www.atmel.com/dyn/resourc...

If you do their div8u for example then inputs are in R16 and R17 and results in R16 and R15 - it's the remainder in R15 that you want as the modulo result

Cliff

PS In case you aren't familiar with Atmel's app notes (but ALL programmers of AVRs should be!) then for the AVR-8 then the complete list is here:

http://www.atmel.com/dyn/product...

and the code to accompany the one I linked above is:

http://www.atmel.com/dyn/resourc...

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

You can get division routines from various sources such as Atmel's application notes (see atmel app note avr200). Most division routines give you the "whole number result" plus any remainder. This remainder is the modulo number you are looking for.

hoyt

When in the dark remember-the future looks brighter than ever.   I look forward to being able to predict the future!

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

Thanks I got it working.

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

One last question,

I was thinking about trying to also implement a version where I could take a 32 byte hex string and do MOD X to it with X is any number from 0 - 256. So take the whole string and MOD it by 3 for example. Is there any implementations of doing that with big numbers?

Thanks for all the help on the previous 1 byte MOD function.

so I guess example:

112233445566778899AABBCCDDEEFF MOD 03

I know the above is not 32 bytes but it is to just show my idea.

Thanks For the Help once again.

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

See I was thinking that I could just add all the bits up and do a division on the final value but that will not work.

I guess I have to do all 128 bits, but can not seem to get a handle on how to appoarch it.

Any advice?

Thanks

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

I think the issue here is the algorithm and requirement, not the math. I've never encountered a problem where a large number like that was needed to be modulo'd with a small base. Maybe your example of 03 is not the order of magnitude you really need.

Perhaps you could share a bit more on the next level up of detail on your goal.

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

Here's some reasonably straightforward assembly code for calculating the Modulo of an arbitrary long number(up to 256 bytes in this case) by an 8bit number.

This is written for WinAVR and is callable from C.

Mod_BigNum_by_u8.S:

#include 

Mod_BigNum_by_u8: .global Mod_BigNum_by_u8
; c-prototype ==> uint8_t Mod_BigNum_by_u8(uint8_t * pBigNum, uint8_t ByteCount, uint8_t Divisor);

; Parameters
    .set pBigNum, 24        ; (u16) pointer to the BigNum Dividend.  Highbyte first
    .set ByteCount, 22      ; (u8) number of bytes in the BigNum
    .set Divisor, 20        ; (u8) Divisor

; Local Variables
    .set BitCount, 23       ; (u8) Number of bits left in the current byte
    .set CurrentByte, 21    ; (u8) Most recently used byte of BigNum

; Return value
    .set Dividend, 24       ; (u16) result (we only need 8bits, but WinAVR requires 16)


; Loop through all bytes of BigNum
    movw ZL, pBigNum        ; move pBigNum to Z
    clr Dividend            ; Dividend starts at zero

_GetNextByte:

; Loop through 8 bits of the current byte
    ld CurrentByte, Z+      ; Get the next byte
    ldi BitCount, 8         ; 8 new bits are ready

_GetNextBit:

    lsl CurrentByte         ; Shift out next bit
    rol Dividend            ; Shift in the next bit

    brcs _DividendOverflow  ; This is only necessary for Divisors > 128

    ; if Dividend < Divisor then skip subtraction
    cp Dividend, Divisor
    brlo _DontSub

_DividendOverflow:
    ; Dividend is >= Divisor, so perform the subtraction
    sub Dividend, Divisor

_DontSub:
    ; do while( --Bitcount != 0)
    dec BitCount
    brne _GetNextBit

    ; do while( --Bytecount != 0)
    dec ByteCount
    brne _GetNextByte


; Done!
    ; Remainder is located in Dividend

    clr Dividend+1          ; extend Remainder to 16bits for WinAVR compatiblity

    ret

And, to exercise the Modulo in C:

#include 

uint8_t Mod_BigNum_by_u8(uint8_t * pBigNum, uint8_t ByteCount, uint8_t Divisor);

uint8_t BigNum[] = { 0xAB, 0xDC, 0x13, 0x18 };  // 0xABDC1318 in order of Highbyte to lowbyte

int main()
{
    uint8_t Divisor = 15;

    uint32_t SmallNumDividend = 0xABDC1318;
    uint8_t SmallNumRemainder = SmallNumDividend % Divisor;

    uint8_t BigNumRemainder = Mod_BigNum_by_u8( BigNum, sizeof(BigNum), Divisor);

    uint8_t GoodResult;
    if( BigNumRemainder == SmallNumRemainder ) {
        // Yea!
        GoodResult = 1;
    } else {
        // Boo!
        GoodResult = 0;
    }

    for(;;)
        ;
}

In the above example, the Modulo takes roughly 10 cycles per bit.

If needed, a Quotient of length equal to BigNum can be calculated with a few trivial mods to the above assembly code.

--Brian

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

Brian thanks for the above code however I have one problem.

I downloaded winavr to compile you C code but I keep getting this message:

Linking: safe.elf
avr-gcc -mmcu=atmega48 -I. -gdwarf-2 -DF_CPU=8000000UL -O0 -funsigned-char -funsigned-bitfields -fpack-struct -fshort-enums -Wall -Wstrict-prototypes -Wa,-adhlns=safe.o -std=gnu99 -MD -MP -MF .dep/safe.elf.d safe.o --output safe.elf -Wl,-Map=safe.map,--cref -lm
safe.o: In function `main':
C:\Documents and Settings\Administrator\Desktop\Atmega Manual/safe.c:14: undefined reference to `Mod_BigNum_by_u8'
make.exe: *** [safe.elf] Error 1

How would I go about fixing this as I am new to winavr.

Thanks

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

The code of the Mod_BigNum_by_u8 routine is in that assembler code Brian gave so you'd need to copy that assembler and store it in a separate file called something like mod.S (note that it's important it has a .S extension and it must be .S and not .s). Now in the Makefile you are using you may find (assuming you used Mfile to generate it) that there's already a line that says:

ASRC=

all you need to do is add mod.S to the list of files on that line, such as:

ASRC=mod.S

Now when you build the C will be compiled, the .S will be assembled and the two resultant .o intermediate files will be linked togther to make the final .elf output.

Cliff

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

Thanks for all the help, almost there just need a little more of your guys knowledge ;-)

Last Edited: Thu. Jul 13, 2006 - 04:31 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Just a quick note. You never initialized r22 ByteCount, except you do decrement it.

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

I just included the function hence why I wrote that little note in the code section to say that I loaded this and that first.

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

Ghostwriter wrote:
Ok I understand that but why is the dividend cleared in the end?

clr Dividend+1 ; extend Remainder to 16bits for WinAVR compatiblity

ret

This makes no sense as I need the remander. I converted the project to just straigth asm as I do not use winavr.


The remainder isn't being cleared; the register located one address above the remainder is being cleared.

The reason why is irrelavent for somebody who isn't actually working with avr-gcc.

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

Thanks for all the help.

Last Edited: Thu. Jul 13, 2006 - 04:32 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

How did you calculate your expected result?

Given your TestVal: (broken into 32byte chunks, to void messing up the forum)

112233445566778899AABBCCDDEEFFFF112233445566778899AABBCCDDEEFFFF...
112233445566778899AABBCCDDEEFFFF112233445566778899AABBCCDDEEFFFF...
112233445566778899AABBCCDDEEFFFF112233445566778899AABBCCDDEEFFFF...
112233445566778899AABBCCDDEEFFFF112233445566778899AABBCCDDEEFFFF

I believe that TestVal Modulo 7 is 2.

I just calculated: TestVal - ( (TestVal IntegerDiv 7) * 7)
..and I came up with 2.

--Brian

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

Yep you were right it was an error in my input.

Everything work perfect, thanks guys for all your help you are the best.