Simulating uint64_t

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

I have an ATMega128A application where I need to shift a field of 12 1s through a 40-bit long number, one bit at a time. It seems to me the easiest way to do this would be to use a uint64_t for the 40-bit number, but my compiler doesn’t support anything longer than 32-bits. I could use a uint32_t and a uint8_t, but there’s probably a better way (bit fields in a structure?) so I thought I’d check in here and see what others thought. I’m neither space nor time constrained, so I’m looking for the clearest solution (i.e. easiest to follow when I look at this code again in a few years). Thanks for any tips.

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

Interesting problem.  I wonder if working on an array uint8_t number[5] might be a little more clean and clear as to intent?

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

Which compiler is it? Could you temporarily change to avr-gcc for this one project as it has 64bit vars.

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

If the 12 ones are consecutive, you have only 40 possible 5-byte values.

They would fit in 200 bytes of flash.

If the 12 ones are consecutive, note that at most 2 bits will change on each shift.

If you need a general shift, go the 8+32 route.

 

BTW is it a circular shift?

Iluvatar is the better part of Valar.

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

I would do something like:

 

typedef struct {
	uint32_t big;
	uint8_t small;
} forty_bit_t;

void shift_right(forty_bit_t * mydata){
	mydata->small >>= 1;
	if (mydata->big & 1)
		mydata->small |= 0x80;
	mydata->big >>=1;
}


int main() {
	forty_bit_t test = {PIND, PIND};
	shift_right(&test);
	return test.small | (test.big << 8);
}

This test program, compiled by gcc, gives a number of bad optimizations, but that's a story for another thread... maybe.

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

lautman wrote:
It seems to me the easiest way to do this would be to use a uint64_t for the 40-bit number, but my compiler doesn’t support anything longer than 32-bits. I could ...

Yah know, instead of switching toolchains, this is one case where a screen-long ASM or mixed snippet for each of the needed operations (I'd think load, test, shift, maybe clear, etc.) might be the shortest imlementation route.  Surely simpler than switching toolchains as one of my esteemed colleagues suggested.  The actual implementation approach might well depend on the toolchain involved.  [For example, if the important part of the application were this manipulation then CodeVision's regiater variables come to mind.

 

As you all know, I often participate in the "you can't do this in C" discussions.  I always have caveats:  If the algorithm can best be served using facilities not in C, such as rotate, and/or carry, and/or variable widths not integral to the toolchain then it will be "interesting" in C.  This posed situation has all of the factors.

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

theusch wrote:

[For example, if the important part of the application were this manipulation then CodeVision's regiater variables come to mind.

 

Exactly what I do for decoding a weird-ass 56 bit serial data stream at high speed.

 

Although CVAVR does support 64-bit maths. Complete with shifts.

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#2 Hardware Problem? Read AVR042.

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."

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

does speed matter ?

 

if it's a circular shift the 200 byte in flash will be relative fast (yes it can be done faster in ASM but it will be in the ballpark of 10 clk, if that matter then we need more information for the use of the data)

 

for a general solution (slow), I would make a bit set and clr function so:

 

init set the first 12 bit

 

next : set 12 clr 0

then   set 13 clr 1

...

 

 

Add :

Using 64 math will be slow if this is a circular buffer, 

  

Last Edited: Thu. Dec 13, 2018 - 05:52 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Jumpstart C (formerly ICCAVR).  If necessary I could use avr-gcc.  Didn't think to check if it supported uint64_ts but just confirmed it did.  Of course, I'd prefer a solution that not only stays within my normal tool chain but is less sensitive to corner cases like this.  I realize uint64_t is part of the standard but, as we can see, it's not universally implemented.

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

Very interesting idea.  Thanks.  I'll think about it.  And, it is a circular shift.

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

I don't think it matters how you do it. The most important part is the comment that says it is what you are doing. Here is a very wasteful way of doing it:

    uint8_t i;
    uint8_t bit[39];
    uint8_t sav;

:

:
// left circular shift an array of 40 bits
    sav = bit[0]; // save the bit being passed from 'left' end to 'right' end
    for (i = 0;i<38;i++) bit[i]=bit[i+1]; // move all the other bits one to the 'left'
    bit[39] = sav; // make the saved bit the 'rightmost' bit

 

I don't think any self respecting programmer would do this because there are so many more efficient ways. My point is the documentation makes it clear what is happening. Come back in 5 years, it still makes sense.

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

While clarity is more important than space or speed (I'm rotating one bit every 45 msec.), I still need the 1s and 0s to ultimately be contiguous.  Your approach requires that the seven leading 0s of each byte in the array be removed to reconstitute the 1s.  I don't mind the wastefulness (I've got 4KB of RAM to play with), but I'm not sure this ends up being the clearest approach.

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

lautman wrote:

I still need the 1s and 0s to ultimately be contiguous.  Your approach requires that the seven leading 0s of each byte in the array be removed to reconstitute the 1s.

It depends on what you are using the bits for. If you are just interested in the individual bits it doesn't matter if the other 7 bits in each byte is 0, you would only be testing for 1 or 0. If you are using a block of bits (say 8 bits to output to a port) then yes you would have to gather the bits from each member of the array. I wasn't serious about that being a good way to do it (I said as much) but as a simplistic (KISS) and well documented way. If I were doing it, I'd do it in assembler because I am an assembler junkie. I am just learning the AVR variant of C++. Caveat - I don't even know how a for statement works yet, I probably mess up in the terminating test. At my level of C knowledge I'd probably:

    uint8_t i;
    uint8_t bits[4];
    uint8_t carryin;
    uint8_t carryout;

:

:
// left circular shift bit array
    carryin = 0 ; // save the bit being passed from 'left' end to 'right' end
    for (i = 4;i==0;i--)
    {
         carryout = bits[i]>127;
         bits[i]=(bits[i]<<1) + carryin;
         carryin=carryout;
    }

    bits[4]+=carryin;

I like the fact only one type of element is used for the bit pattern, and it occupies the right amount of space. And maybe the compiler can optimise as it is a byte array and we are dealing with an 8-bit processor. I make the assumption that true=1 and false=0 but I don't know if that's correct (I shall check the doco later). I also assume there's some way of overlaying the array to extract the bits you want. Lots of assumptions that can be checked in the doco of your compiler.

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

ajcashin wrote:

I don't think any self respecting programmer would do this because there are so many more efficient ways....

 

Putting in a horribly-time-wasting but easy-to-get-working

version of an algorithm is often a great approach.  Get all

of the functionality working, then decide where you need

to fine-tune the performance.  The crap version may be

good enough!

 

--Mike

 

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

avr-mike wrote:

ajcashin wrote:

 

I don't think any self respecting programmer would do this because there are so many more efficient ways....

 

Putting in a horribly-time-wasting but easy-to-get-working

version of an algorithm is often a great approach.  Get all

of the functionality working, then decide where you need

to fine-tune the performance.  The crap version may be

good enough!

 

--Mike

 

I agree with the first part - start off with the easy version first. Much of my logic gets tested in .vbs scripts before making it into its intended context (should I even admit that?). Although the crap version may be good enough in the particular situation I would still be tempted to refine it. Because somewhere down the track you're going to say "I wrote that 40 bit shift before" - cut and paste or include. And that next time might be more constrained. A boss of mine said "Do it right, do it once" and I've thought that's a reasonable approach.

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

lautman wrote:

Very interesting idea.  Thanks.  I'll think about it.  And, it is a circular shift.

So if it is circular you don't need to move the data, you just alter pointers into that data.

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#2 Hardware Problem? Read AVR042.

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."

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

I don't mind admiting that I haven't a clue as to what the OP is trying to achieve, so am finding it difficult to join in the challenge.

 

@lautman

Please post a quick & dirty function that demonstrates your intention. If you use an array of 40 bytes instead if bits that would probably be better for getting across your requirement.

 

 

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

It would be useful if the OP would post some bare-bones code using uint64_t, so we can get a better idea of what he wants to do.

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

I thought OP was clear.

OP wants 5 contiguous bytes in memory.

The region should have 28 0 bits and 12 contiguous 1 bits.

OP want to be able to do a circular shift.

Admittedly, I'm not clear on whether

OP wants a left or right circular shift.

 

Whether OP would be wiser to want

something else is a separate question.

Iluvatar is the better part of Valar.

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

skeeve wrote:

... OP wants 5 contiguous bytes in memory. The region should have 28 0 bits and 12 contiguous 1 bits...OP want to be able to do a circular shift...

If that is all the OP wants then you don't actually need to store anything as you can easily create the result on the fly from just a single 8-bit value.

#1 Hardware Problem? https://www.avrfreaks.net/forum/...

#2 Hardware Problem? Read AVR042.

#3 All grounds are not created equal

#4 Have you proved your chip is running at xxMHz?

#5 "If you think you need floating point to solve the problem then you don't understand the problem. If you really do need floating point then you have a problem you do not understand."