Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Date | 2012-04-17 12:49 +0200 |
|---|---|
| From | Terje Mathisen <"terje.mathisen at tmsw.no"> |
| Newsgroups | comp.arch |
| Subject | Re: Indirect Bit |
| References | <4F84FB1E.6CD1FC88@sonic.net> <5623c8b4-715e-4ee3-8440-ed4331416aee@z3g2000vbk.googlegroups.com> <jmhjnc$770$1@needham.csi.cam.ac.uk> <9v3noiFchsU1@mid.individual.net> <jmj93k$9v6$1@needham.csi.cam.ac.uk> |
| Message-ID | <ifuv59-ol61.ln1@ntp6.tmsw.no> (permalink) |
nmm1@cam.ac.uk wrote:
> I tried to code several important primitives on some and, in my
> usual fashion, tried to get them right for all cases. Ugh. And
> optimising compilers have serious problems producing good code
> when its tricky to do so even by hand. This was for things like
> (A*B)/C->(quot,rem) with reliable overflow detection and no spurious
> overflow.
:-)
That one is dead simple if you have both N*N->2N multiply and
2N/N->(N,N) division, if you don't, then things become "slightly" more
complicated.
Using just portable 32-bit C, and unsigned only, you'll still need quite
a bit of code...
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c, uint32_t *rem)
{
uint32_t abl, abm1, abm2, abh;
// None of the following operations can overflow
// Do the 4 16*16->32 multiplications:
abl = (a & 0xffff) * (b & 0xffff);
abm1 = (a & 0xffff) * (b >> 16);
abm2 = (a >> 16) * (b & 0xffff);
abh = (a >> 16) *(b >> 16);
// Merge into low/high result:
abh += (abm1 >> 16) + (abm2 >> 16);
abm1 = (abm1 & 0xffff) + (abm2 & 0xffff) + (abl >> 16);
// Generate final abh:abl result:
abh += abm1 >> 16;
abl = (abl & 0xffff) | (abm1 << 16);
// Now for the division part:
// The division will overflow if C <= ABH, this includes the C==0 case
// Return (0,C) if so:
if (c <= abh) {
*rem = c;
return 0;
}
// At this point the fastest approach depends on the magnitude of C:
// C < 64K: Use repeated 32/16 -> 16 divisions
// C >= 64K: Do trial divisions using the top 16 bits of C
// Fast fp? Calculate reciprocal and approximate answer,
// adjust with a final loop.
}
The amount of code required does blow up pretty quickly when you don't
have those N-2N operations!
Compare with x86 asm:
uint32_t muldiv(uint32_t a, uint32_t b, uint32_t c, uint32_t *rem)
{
__asm {
mov eax,[a]
mul [b]
div [c] // Can trap here!
mov ebx,[rem]
mov [ebx],edx
}
}
Terje
--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"
Back to comp.arch | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Indirect Bit Mark Thorson <nospam@sonic.net> - 2012-04-10 19:31 -0800
Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-11 01:29 -0500
Re: Indirect Bit sarr.blumson@alum.dartmouth.org - 2012-04-11 14:48 +0000
Re: Indirect Bit mac <acolvin@efunct.com> - 2012-04-12 14:43 +0000
Re: Indirect Bit Morten Reistad <first@last.name> - 2012-04-22 15:19 +0200
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-22 23:24 -0700
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-11 08:32 +0200
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-11 05:49 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:22 -0700
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-13 08:14 -0700
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-13 16:13 -0700
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-13 20:01 -0700
Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-14 03:16 +0000
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-14 08:14 -0700
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-13 16:05 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-13 17:01 -0700
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-14 13:49 -0700
Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-13 20:07 -0400
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-14 18:47 +0200
Re: Indirect Bit Morten Reistad <first@last.name> - 2012-04-22 15:26 +0200
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-22 23:25 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 09:18 +0100
Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-23 19:35 -0400
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 08:37 +0100
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 09:42 +0100
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 01:58 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 11:26 +0100
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 05:02 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 13:58 +0100
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 10:07 -0700
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-24 04:30 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-24 13:01 +0100
Re: Indirect Bit Stefan Monnier <monnier@iro.umontreal.ca> - 2012-04-11 10:03 -0400
Re: Indirect Bit kenney@cix.compulink.co.uk - 2012-04-11 09:22 -0500
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-12 14:11 -0700
Re: Indirect Bit Stefan Monnier <monnier@iro.umontreal.ca> - 2012-04-12 18:05 -0400
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 20:13 -0700
Re: Indirect Bit Mark Thorson <nospam@sonic.net> - 2012-04-12 16:55 -0800
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-12 17:25 -0700
Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-12 20:03 -0500
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:33 -0700
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-13 15:57 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-13 17:03 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 20:14 -0700
Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-11 10:35 -0400
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-11 08:54 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 07:55 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-12 10:16 -0700
Re: Indirect Bit jacko <jackokring@gmail.com> - 2012-04-12 11:07 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:34 -0700
Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-12 11:35 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:41 -0700
Re: Indirect Bit jacko <jackokring@gmail.com> - 2012-04-13 14:52 -0700
Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-15 09:24 -0700
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-15 22:45 +0200
Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-15 18:04 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-12 21:12 -0700
Re: Indirect Bit timcaffrey@aol.com (Tim McCaffrey) - 2012-04-12 19:23 +0000
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-13 08:54 +0200
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-14 14:37 -0700
Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-15 23:42 +0000
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-16 08:08 -0700
Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-16 23:38 +0000
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-16 21:29 -0700
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-16 21:25 -0700
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-12 14:05 -0700
Re: Indirect Bit ChrisQ <blackhole@devnull.com> - 2012-04-14 10:12 +0000
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-14 06:25 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-14 14:50 +0100
Re: Indirect Bit ChrisQ <blackhole@devnull.com> - 2012-04-14 18:01 +0000
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-14 14:00 -0700
Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-14 20:58 -0400
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-16 09:57 -0700
Re: Indirect Bit timcaffrey@aol.com (Tim McCaffrey) - 2012-04-20 23:19 +0000
Re: Indirect Bit "Paul A. Clayton" <paaronclayton@gmail.com> - 2012-04-16 08:50 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-16 18:09 +0100
Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-16 23:19 +0000
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-17 09:20 +0100
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-17 12:49 +0200
Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-17 12:40 +0000
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-18 12:01 +0100
Re: Indirect Bit anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-04-17 12:34 +0000
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-17 09:10 -0700
Re: Indirect Bit Andrew Reilly <areilly.---@bigpond.net.au> - 2012-04-17 22:05 +0000
Re: Indirect Bit jgk@panix.com (Joe keane) - 2012-04-19 19:37 +0000
Re: Indirect Bit torbenm@diku.dk (Torben Ægidius Mogensen) - 2012-04-20 11:10 +0200
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-20 11:24 +0200
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-20 15:01 +0100
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-20 15:03 +0100
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-20 08:01 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-20 16:35 +0100
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-18 11:10 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-18 15:37 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-16 11:21 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-16 19:36 +0100
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-18 11:17 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-18 15:33 -0700
Re: Indirect Bit Andreas Eder <andreas_eder@gmx.net> - 2012-04-19 00:29 +0200
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-19 10:50 +0100
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-19 11:29 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-19 21:39 +0100
Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-20 15:14 -0400
Re: Indirect Bit "Andy (Super) Glew" <andy@SPAM.comp-arch.net> - 2012-04-20 22:43 -0700
Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-21 17:14 -0400
Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-21 19:47 -0500
Re: Indirect Bit Nomen Nescio <nobody@dizum.com> - 2012-04-22 10:45 +0200
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 09:57 +0100
Re: Indirect Bit Terje Mathisen <"terje.mathisen at tmsw.no"> - 2012-04-22 12:54 +0200
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 13:00 +0100
Re: Indirect Bit Nomen Nescio <nobody@dizum.com> - 2012-04-22 13:28 +0200
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 13:04 +0100
Re: Indirect Bit Fritz Wuehler <fritz@spamexpire-201204.rodent.frell.theremailer.net> - 2012-04-22 23:00 +0200
Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-22 18:05 -0400
Re: Indirect Bit glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-04-22 23:20 +0000
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 08:22 +0100
Re: Indirect Bit Michael S <already5chosen@yahoo.com> - 2012-04-22 03:56 -0700
Re: Indirect Bit EricP <ThatWouldBeTelling@thevillage.com> - 2012-04-22 12:28 -0400
Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-22 12:56 -0500
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-22 13:15 -0700
Re: Indirect Bit Nomen Nescio <nobody@dizum.com> - 2012-04-22 22:30 +0200
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-22 21:40 +0100
Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-22 17:15 -0500
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 08:26 +0100
Re: Indirect Bit Stephen Fuld <SFuld@alumni.cmu.edu.invalid> - 2012-04-23 08:02 -0700
Re: Indirect Bit nmm1@cam.ac.uk - 2012-04-23 17:02 +0100
Re: Indirect Bit Fritz Wuehler <fritz@spamexpire-201204.rodent.frell.theremailer.net> - 2012-04-23 20:17 +0200
Re: Indirect Bit Robert Wessel <robertwessel2@yahoo.com> - 2012-04-23 13:07 -0500
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-22 13:16 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-23 13:14 -0700
Re: Indirect Bit Anne & Lynn Wheeler <lynn@garlic.com> - 2012-04-23 16:51 -0400
Re: Indirect Bit Quadibloc <jsavard@ecn.ab.ca> - 2012-04-23 14:22 -0700
Re: Indirect Bit MitchAlsup <MitchAlsup@aol.com> - 2012-04-21 11:17 -0700
Re: Indirect Bit jacko <jackokring@gmail.com> - 2012-04-14 08:02 -0700
csiph-web