Hello,
Unfortunately, my compiler (GCC) doesn't seem to support 96-bit or 128-bit ints, so I have to roll my own. My current problem is that I can't find a way to implement left or right shifts efficiently. How is it done?
Tord
How to implement shifts?
Moderators: hgm, Rebel, chrisw
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: How to implement shifts?
Run gcc on a strictly 32 bit system and see how it generates 64 bit integer shifts. Use analogical reasoning to extend the generated assembly language to handle 128 bit shifts on a 64 bit system.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: How to implement shifts?
That's what I hoped to avoid. There are few things I hate more than trying to read assembly language.sje wrote:Run gcc on a strictly 32 bit system and see how it generates 64 bit integer shifts.
Actually, I use a 32 bit system, but that probably doesn't make any difference for the algorithm.Use analogical reasoning to extend the generated assembly language to handle 128 bit shifts on a 64 bit system.
Tord
-
- Posts: 2055
- Joined: Mon Mar 13, 2006 2:31 am
- Location: North Carolina, USA
Re: How to implement shifts?
Here goes a top of my head manual effort.
You have two locations Hi and Lo each are 64 bit.
You want to shift left B bits which means carry over the
leftmost B bits in Lo to the lower B bits in Hi. I am assuming
both Hi and Lo are unsigned.
Shift right could be implement similarly.
You have two locations Hi and Lo each are 64 bit.
You want to shift left B bits which means carry over the
leftmost B bits in Lo to the lower B bits in Hi. I am assuming
both Hi and Lo are unsigned.
Code: Select all
int B;
unsigned long long upperbits, Hi, Lo;
upperbits = -1; // fill upperbits with 1s
upperbits = upperbits << (64 - B); // creates mask for upper bits
upperbits = Lo & upperbits; // save the upperbits of Lo
Lo = Lo << B;
Hi = (Hi << B) | (upperbits >> (64-B));
-
- Posts: 373
- Joined: Wed Mar 22, 2006 10:17 am
- Location: Novi Sad, Serbia
- Full name: Karlo Balla
Re: How to implement shifts?
I dont know if my implementation is correct but look niceCRoberson wrote:Here goes a top of my head manual effort.
You have two locations Hi and Lo each are 64 bit.
You want to shift left B bits which means carry over the
leftmost B bits in Lo to the lower B bits in Hi. I am assuming
both Hi and Lo are unsigned.
Shift right could be implement similarly.Code: Select all
int B; unsigned long long upperbits, Hi, Lo; upperbits = -1; // fill upperbits with 1s upperbits = upperbits << (64 - B); // creates mask for upper bits upperbits = Lo & upperbits; // save the upperbits of Lo Lo = Lo << B; Hi = (Hi << B) | (upperbits >> (64-B));
Code: Select all
int B;
unsigned long long Hi, Lo;
Hi = (Hi << B) | (Lo >> (64-B));
Lo = Lo << B;
Best Regards,
Karlo Balla Jr.
Karlo Balla Jr.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: How to implement shifts?
Charles and Karlo,
Thanks for your replies! Both solutions look rather more expensive than I would like (several shifts, a subtraction, a binary OR), but perhaps there is nothing better. At least I haven't been able to find something better myself yet.
Tord
Thanks for your replies! Both solutions look rather more expensive than I would like (several shifts, a subtraction, a binary OR), but perhaps there is nothing better. At least I haven't been able to find something better myself yet.
Tord
Re: How to implement shifts?
"Hackers delight" has some examples of multi-word shifts.
Here is a sample implementation of mine:
The book contains a branchless version of the singed shift as well if your interested.
Here is a sample implementation of mine:
Code: Select all
/**
* 128 Bit Integer
*/
public class XLong {
long hi;
long lo;
void shiftLeft(int n){
long yhi = (hi << n) | (lo >>> (64 - n)) | (lo << (n - 64));
long ylo = lo << n;
hi = yhi;
lo = ylo;
}
void shiftRightUnsigned(int n){
long ylo = (lo >>> n) | (hi << (64 - n)) | (hi >>> (n - 64));
long yhi = hi >>> n;
hi = yhi;
lo = ylo;
}
void shiftRightSigned(int n){
long ylo;
if(n < 64){
ylo = (lo >>> n) | (hi << (64 - n));
}else{
ylo = hi >> (n - 64);
}
long yhi = hi >> n;
hi = yhi;
lo = ylo;
}
}
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How to implement shifts?
In assembly, it's ASL/ASR combined with ROL (arithemetic shift left/right, then roll over of the carry bit)Tord Romstad wrote:Hello,
Unfortunately, my compiler (GCC) doesn't seem to support 96-bit or 128-bit ints, so I have to roll my own. My current problem is that I can't find a way to implement left or right shifts efficiently. How is it done?
Tord
Maybe something like this can be helpful:
#define UINT_BIT (sizeof (unsigned) * CHAR_BIT)
unsigned rollWithCarryRight(unsigned value, unsigned *carryFlag)
{
unsigned carryFlagContents = *carryFlag;
*carryFlag = value & 1;
return (value >> 1) || (carryFlagContents << (UINT_BIT - 1));
}
Obviously, the same idea scales to any unsigned integer size.
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How to implement shifts?
Here is the MS VC++ code for shifting right and left 64 bit integers using 32 bit integers. In assembly, of course.
;***
;llshl - long shift left
;
;Purpose:
; Does a Long Shift Left (signed and unsigned are identical)
; Shifts a long left any number of bits.
;
;Entry:
; EDX:EAX - long value to be shifted
; CL - number of bits to shift by
;
;Exit:
; EDX:EAX - shifted value
;
;Uses:
; CL is destroyed.
;
;Exceptions:
;
;*******************************************************************************
CODESEG
_allshl PROC NEAR
;
; Handle shifts of 64 or more bits (all get 0)
;
cmp cl, 64
jae short RETZERO
;
; Handle shifts of between 0 and 31 bits
;
cmp cl, 32
jae short MORE32
shld edx,eax,cl
shl eax,cl
ret
;
; Handle shifts of between 32 and 63 bits
;
MORE32:
mov edx,eax
xor eax,eax
and cl,31
shl edx,cl
ret
;
; return 0 in edx:eax
;
RETZERO:
xor eax,eax
xor edx,edx
ret
;***
;ullshr - long shift right
;
;Purpose:
; Does a unsigned Long Shift Right
; Shifts a long right any number of bits.
;
;Entry:
; EDX:EAX - long value to be shifted
; CL - number of bits to shift by
;
;Exit:
; EDX:EAX - shifted value
;
;Uses:
; CL is destroyed.
;
;Exceptions:
;
;*******************************************************************************
CODESEG
_aullshr PROC NEAR
;
; Handle shifts of 64 bits or more (if shifting 64 bits or more, the result
; depends only on the high order bit of edx).
;
cmp cl,64
jae short RETZERO
;
; Handle shifts of between 0 and 31 bits
;
cmp cl, 32
jae short MORE32
shrd eax,edx,cl
shr edx,cl
ret
;
; Handle shifts of between 32 and 63 bits
;
MORE32:
mov eax,edx
xor edx,edx
and cl,31
shr eax,cl
ret
;
; return 0 in edx:eax
;
RETZERO:
xor eax,eax
xor edx,edx
ret
;***
;llshl - long shift left
;
;Purpose:
; Does a Long Shift Left (signed and unsigned are identical)
; Shifts a long left any number of bits.
;
;Entry:
; EDX:EAX - long value to be shifted
; CL - number of bits to shift by
;
;Exit:
; EDX:EAX - shifted value
;
;Uses:
; CL is destroyed.
;
;Exceptions:
;
;*******************************************************************************
CODESEG
_allshl PROC NEAR
;
; Handle shifts of 64 or more bits (all get 0)
;
cmp cl, 64
jae short RETZERO
;
; Handle shifts of between 0 and 31 bits
;
cmp cl, 32
jae short MORE32
shld edx,eax,cl
shl eax,cl
ret
;
; Handle shifts of between 32 and 63 bits
;
MORE32:
mov edx,eax
xor eax,eax
and cl,31
shl edx,cl
ret
;
; return 0 in edx:eax
;
RETZERO:
xor eax,eax
xor edx,edx
ret
;***
;ullshr - long shift right
;
;Purpose:
; Does a unsigned Long Shift Right
; Shifts a long right any number of bits.
;
;Entry:
; EDX:EAX - long value to be shifted
; CL - number of bits to shift by
;
;Exit:
; EDX:EAX - shifted value
;
;Uses:
; CL is destroyed.
;
;Exceptions:
;
;*******************************************************************************
CODESEG
_aullshr PROC NEAR
;
; Handle shifts of 64 bits or more (if shifting 64 bits or more, the result
; depends only on the high order bit of edx).
;
cmp cl,64
jae short RETZERO
;
; Handle shifts of between 0 and 31 bits
;
cmp cl, 32
jae short MORE32
shrd eax,edx,cl
shr edx,cl
ret
;
; Handle shifts of between 32 and 63 bits
;
MORE32:
mov eax,edx
xor edx,edx
and cl,31
shr eax,cl
ret
;
; return 0 in edx:eax
;
RETZERO:
xor eax,eax
xor edx,edx
ret
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How to implement shifts?
Don't know if it will help in general, but there seems to be an intrinsic for 128 bit shifts on Apple computers:
http://developer.apple.com/documentatio ... ion_2.html
This looks useful:
http://www.math.sci.hiroshima-u.ac.jp/~ ... 062821.pdf
The Jikes compiler:
http://sourceforge.net/project/showfile ... _id=128803
has long.cpp and long.h which implement 64 bit integers in terms of 32 bit integers as a number class with overloaded operators. I guess that it would be a great model, as the results would be very convenient to use when doubled in size to 128 bits.
http://developer.apple.com/documentatio ... ion_2.html
This looks useful:
http://www.math.sci.hiroshima-u.ac.jp/~ ... 062821.pdf
The Jikes compiler:
http://sourceforge.net/project/showfile ... _id=128803
has long.cpp and long.h which implement 64 bit integers in terms of 32 bit integers as a number class with overloaded operators. I guess that it would be a great model, as the results would be very convenient to use when doubled in size to 128 bits.