zweig@cs.uiuc.edu (Johnny Zweig) (02/04/91)
In my work with the TCP/IP protocol suite, I have had to implement 16-bit 1's-complement arithmetic in a protable, efficient way for protocol processing modules. In case you're rusty, ones-complement addition is exactly ordinary twos-complement addition with carry (i.e. 101 + 111 = 101 in 3-bit 1's complement since the 1 carried out of the left goes "end around" to the low order bits -- 111 thus is "-0"). Every microprocessor I've ever seen the assembly language instruction set for has, in addition to ordinary twos-complement addition instructions, some kind of "add with carry" instruction which, while not actually implementing ones complement arithmetic (to add A and B in ones complement, you execute A + B add-with-carry 0), is just what the doctor ordered for doing IP checksum computations, and many other iterative ones-complement arithmetic computations. The problem: there is not an add-with-carry operator in C++, so there isn't any way of writing portable code to use this. I know, I know, I know, I can be totally gross and icky and hard and use asm's and come up with a different one for each processor/compiler combination I want to run on. But if there were a standard way of letting the compiler know that I want to do add-with-carry rather than vanilla add I could write portable, efficient code that people like Van Jacobson would think was swell. I suppose that a properly inlined function could do the trick, but it would be nice if there were an operator. Comments? -Johnny Ones
dhoyt@vx.acs.umn.edu (DAVID HOYT) (02/05/91)
In article <1991Feb3.202530.14874@julius.cs.uiuc.edu>, zweig@cs.uiuc.edu (Johnny Zweig) writes... >The problem: there is not an add-with-carry operator in C++, so there isn't >any way of writing portable code to use this. You can write add with carry code that will work portably with all 2's complement machines. Unless you're writing code for some special embedded processor you can hit 100% of the machines out there with one source program and no ifdefs, and if you are writing for an embedded processor you aren't interested in portable code anyway. I vote no for this one. The algorithm is, of course, left up to the reader (hint it was solved a looong time ago). david | dhoyt@vx.acs.umn.edu | dhoyt@vx.acs.umn.edu
jimad@microsoft.UUCP (Jim ADCOCK) (02/05/91)
In article <1991Feb3.202530.14874@julius.cs.uiuc.edu> zweig@cs.uiuc.edu writes: | |The problem: there is not an add-with-carry operator in C++, so there isn't |any way of writing portable code to use this. I know, I know, I know, I can be |totally gross and icky and hard and use asm's and come up with a different one |for each processor/compiler combination I want to run on. But if there were a |standard way of letting the compiler know that I want to do add-with-carry |rather than vanilla add I could write portable, efficient code that people |like Van Jacobson would think was swell. I suppose that a properly inlined |function could do the trick, but it would be nice if there were an operator. | |Comments? On my machine/compiler, the following example generates code close to what one would generate by hand in assembler. Thus, one has an example showing it's not necessary for the language to add a add-plus-carry command -- good optimizers can generate such commands where implied by code. I believe compilers ought to offer built-in support for word sizes to 2X the natural bit-size of the machine. Thus, for example, 32-bit machines ought to support code generation for 64-bit integer arithmetic. Whether 64-bit arithmetic on a 32-bit machine ought to be called "long long" or just "long" remains debatable. /* assumes: 8 bits per byte two's complement sizeof(short) < sizeof(long) */ #define bitsperbyte 8 class longlong { private: unsigned short s[4]; public: longlong(long); const longlong& operator+=(const longlong& p); void print(); }; longlong::longlong(long l) { s[0] = (unsigned short)l; s[1] = (unsigned short)(l >> (bitsperbyte * sizeof(unsigned short))); s[2] = s[3] = (l >= 0) ? (unsigned short)0 : (unsigned short)-1;; } const longlong& longlong::operator+=(const longlong& p) { long accum; accum = (long) s[0] + p.s[0]; // unwrapped loop: s[0] = (unsigned short)accum; accum = ((unsigned short)(accum >> (bitsperbyte * sizeof(unsigned short)))) + (long) s[1] + p.s[1]; s[1] = (unsigned short)accum; accum = ((unsigned short)(accum >> (bitsperbyte * sizeof(unsigned short)))) + (long) s[2] + p.s[2]; s[2] = (unsigned short)accum; accum = ((unsigned short)(accum >> (bitsperbyte * sizeof(unsigned short)))) + (long) s[3] + p.s[3]; s[3] = (unsigned short)accum; return *this; } extern "C" void printf(const char*, ...); void longlong::print() { printf("%04X%04X%04X%04X\n", s[3], s[2], s[1], s[0]); } main() { longlong a(0x12345678L); a.print(); longlong b(0xEDCBA988L); b.print(); a += b; a.print(); return 0; }
egr@contact.uucp (Gordan Palameta) (02/07/91)
In <1991Feb3.202530.14874@julius.cs.uiuc.edu> zweig@cs.uiuc.edu (Johnny Zweig) writes: >In my work with the TCP/IP protocol suite, I have had to implement 16-bit >1's-complement arithmetic in a protable, efficient way for protocol processing >[rest of article omitted] To add-with-carry two 16-bit numbers in a portable way: - convert them to unsigned 32-bit (high word zero-filled) - add them to get a 32-bit result (normal addition, ie 2's complement) - take the upper 16 bits and lower 16 bits and add them together, getting a 32-bit result - do previous step again (important!) The lower 16 bits will be your answer (the upper 16 bits will be zero-filled). Try the tcp-ip newsgroup for any further info...