Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!hellgate.utah.edu!caen!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!zweig
From: zweig@cs.uiuc.edu (Johnny Zweig)
Newsgroups: comp.lang.c++
Subject: Re: Add-with-carry operator
Message-ID: <1991Feb6.210332.12826@julius.cs.uiuc.edu>
Date: 6 Feb 91 21:03:32 GMT
References: <1991Feb3.202530.14874@julius.cs.uiuc.edu> <3189@ux.acs.umn.edu>
Sender: news@julius.cs.uiuc.edu (USENet News)
Reply-To: zweig@cs.uiuc.edu
Organization: U of Illinois, Dept. of Computer Science, Systems Research Group
Lines: 93


Peter Deutsch sent me the following piece of email:

From deutsch@parcplace.com Mon Feb  4 12:05:07 1991
Date: Mon, 4 Feb 91 09:59:50 PST
From: deutsch@parcplace.com (Peter Deutsch)
To: zweig@cs.uiuc.edu
Subject: Add-with-carry
Status: OR

Please post this to comp.lang.c++ for me: our mail posting software is
permanently broken.

I too have wanted to do add-with-carry in C, so I found the next best
thing: an algorithmic hack to avoid needing it.  Here is the code for
computing z=x+y, with cin and cout being carry-in and carry-out
respectively (0 or 1).  x, y, and z must all be declared as >>unsigned<<.

	if ( cin )
	  cout = (x >= ~y ? 1 : 0),
	  z = x + y + 1;
	else
	  cout = (x > ~y ? 1 : 0),
	  z = x + y;

If you are doing accumulate-with-carry over an array, the best thing to do
is probably a split loop, something like this:

	/* Assume cin=0 to start */
	unsigned accum = 0;
	unsigned i = 0;
	unsigned elt;
	for ( ; ; )
	 {
carry0:	   if ( i >= count ) break;
	   elt = data[i]; i++;
	   if ( elt > ~accum )
	    { accum += elt; goto carry1; }
	   else
	    { accum += elt; goto carry0; }
carry1:	   if ( i >= count ) break;
	   elt = data[i]; i++;
	   if ( elt >= ~accum )
	    { accum += elt + 1; goto carry1; }
	   else
	    { accum += elt + 1; goto carry0; }
	 }
----------------------------------------------------------------------------
While I appreciate that it's doable (and I appreciate David's comment that
this problem was solved "a looooonnnnnngggg time ago") I _still_ don't think
this addresses my basic point:

	WHY SHOULD I HAVE TO WRITE CODE THAT PERFORMS OPERATIONS THAT ARE
	UNNECESSARY ON EVERY MICROPROCESSOR PRODUCED WITHIN THE LAST 10
	YEARS?

I know the trick of holding the carry bits somewhere else (my code does 16-bit
2's complement adds in 32-bit words and uses the high order bits to hang on to
the carry bits).  I see Peter's solution, though it involves comparisons that
will also add to my instruction-count.  My officemate reminded me that G++ can
do an inline asm() in a library which expands to add-with-carry (though since
the language makes no guarantees about keeping the carry bit in your context,
it isn't clear that even this will always produce correct code).

Maybe I have gotten spoiled by the fact that, in general, I can write C/C++
code that I can think of as portable assembly language. I think the fact that
the language doesn't have a carry bit or a way of setting/clearing/using it
for calculations is an omission (God help me when Bjarne hears that!!).  If
someone has a straightforward way (not left as an exercise to the reader) that
I can produce:

	movl	a0@+, d2	| fetch 32-bit word
	addxl	d2,d0		| add it along with previous carry
	movl	a0@+, d2	| fetch 32-bit word
	addxl	d2,d0		| add it along with previous carry
	movl	a0@+, d2	| fetch 32-bit word
	addxl	d2,d0		| add it along with previous carry

on my 68020 from something along the lines of:

	for(i = 0; i < length; i++) {
	    sum = add_with_carry( sum, p[i] );
	}

and the moral equivalent of the given assembly code on my Sparc, I would love
to hear it.  Maybe it isn't worth it -- I am willing to concede that. But
given the closeness of the virtual machine model C++ has with that of most
major microprocessor vendors (in terms of 8-,16-,32-bit words, indirect
addressing, and that sort of thing) it has always bugged me (pun intended)
that there is not a machine-independent way of talking about carry bits (and,
for that matter, sign and overflow bits) within the language.

-Johnny Carry