Dynamically resizing a buffer

[lawrence.jones@ugs.com]

Re: Dynamically resizing a buffer

Joe Wright <joewwright@com cast.netwrote:

>
Shifting left (mult) seems to be well defined for both signed and
unsigned integers. It is shifting right (div) which is proplematic for
negative signed integers. The question is whether the implementation
copies the sign bit into the msb of the signed value.
>
Consider:
11111100 a signed char with value -4
Shifting it left with yield
11111000 a signed char with value -8

Try it again in ones' complement instead of two's complement:
11111100 a signed char with value -3
Shifting it left will yield
11111000 a signed char with value -7

That certainly doesn't match any definition of multiplication by two
that I'm familiar with.

-Larry Jones

I wonder if you can refuse to inherit the world. -- Calvin

[Richard Bos]

Re: Dynamically resizing a buffer

Joe Wright <joewwright@com cast.netwrote:

CBFalconer wrote:

Flash Gordon wrote:

The shift operator is a basic operator for moving bits, using it
to divide is a trick and one that does not work in all situations.

Actually, the shift operator is defined in terms of division or
multiplication, IIRC. This is just one more reason it should not
be used on negative values. Use of unsigned is safe.

>
Shifting left (mult) seems to be well defined for both signed and
unsigned integers.

On the contrary. It is left-shifting which is completely undefined for
signed integers, if it overflows or if the original value was negative.

It is shifting right (div) which is proplematic for negative signed
integers. The question is whether the implementation copies the sign
bit into the msb of the signed value.

It's worse than that, as well; for negative signed values, the result of
a right-shift is implementation-defined. This was presumably done to
allow both of your options, but it allows less expected ones as well.

That's for C99, btw. In C89 the situation is even worse; it doesn't
completely define what happens to a left-shifted signed value at all,
not even if the value is positive and does not overflow.

Richard

[Joe Wright]

Re: Dynamically resizing a buffer

CBFalconer wrote:

Joe Wright wrote:

>CBFalconer wrote:
>>

... snip ...

>>Actually, the shift operator is defined in terms of division or
>>multiplicatio n, IIRC. This is just one more reason it should not
>>be used on negative values. Use of unsigned is safe.

>Shifting left (mult) seems to be well defined for both signed and
>unsigned integers. It is shifting right (div) which is proplematic
>for negative signed integers. The question is whether the
>implementati on copies the sign bit into the msb of the signed value.

>
What about overflow during integer shifts? Not all right shifts
are arithmetic, some are also logical. Another flavor (not seen in
C systems) is through the carry.
>

Overflow on right shift? I expect right shift of signed integers to
preserve the sign bit. Unsigned integers will have 0 shifted into the
msb. I do miss the carry bit from ASM days.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[CBFalconer]

Re: Dynamically resizing a buffer

Joe Wright wrote:

>

.... snip ...

>
Overflow on right shift?

Very rare on right shifts. Common on left shifts.

I expect right shift of signed integers to preserve the sign bit.
Unsigned integers will have 0 shifted into the msb. I do miss the
carry bit from ASM days.

Those are arithmetic versus logical shifts. Thru carry doesn't
exist in higher languages.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>



--
Posted via a free Usenet account from http://www.teranews.com

[Flash Gordon]

Re: Dynamically resizing a buffer

cr88192 wrote, On 25/08/07 05:00:

"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
news:egn3q4x16e .ln2@news.flash-gordon.me.uk...

>cr88192 wrote, On 24/08/07 02:46:

>>"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
>>news:1ru0q4xk 0o.ln2@news.fla sh-gordon.me.uk...
>>>cr88192 wrote, On 23/08/07 16:09:
>>>>"Flash Gordon" <spam@flash-gordon.me.ukwro te in message
>>>>news:ck60q4 x2tf.ln2@news.f lash-gordon.me.uk...
>>>>>cr88192 wrote, On 23/08/07 11:12:
>>>><snip>
>>>>>
>>>>>>not optimizations. shifts are how one typically does these things...
>>>>>Not if one is being sensible.
>>>>>>
>>>>>>it is much the same as why we call int variables i, j, and k I think,
>>>>>>or many other common practices. after enough years, and enough code,
>>>>>>one largely forgets any such reasoning, all rote response really...
>>>>>I have spent years programming in assembler where I would use shifts
>>>>>and years spent programming in high level languages where I would not.
>>>>yeah, I also use assembler...
>>>>>
>>>>otherwise :
>>>>>
>>>>I always used shifts, never thought much of it.
>>>>I use shifts where I think shifts, I had never thought to think
>>>>divides.. .
>>>>>
>>>>if I were thinking of a divide, than i/3 is an obvious difference from
>>>>i/2. if I was not, it is not.
>>>>it is a non-obvious jump from 'i>>1' to 'i/3', unless one first thinks
>>>>that 'i>>1' is actually 'i/2'...
>>>You are trying to reduce a number by a factor not trying to move bits.
>>>They are conceptually different things. Try using a shit to halve a
>>>floating point number as see how far it gets you.
>>>>
>>but, a float and an integer are different concepts though...
>>not sure of why one would consider using a shift on a float...

>Because you consider shift an appropriate method of halving a number.

>
as noted, if that number is an integer.
>
I personally regard integers and non-integers as different concepts, with
different behaviors, semantics, and rules.

As previously noted, you would have to consider unsigned and signed as
different because right shifting negative numbers is not guaranteed to
act as division.

after all, with integers, 3/4==0, but with non-integers or reals, the answer
is 0.75...

Now implement a scaling of 3/11 with shifts.

likewise I consider reals and complexes to be different concepts.
>
>

>>>>>>actuall y, had I been thinking of compiler behavior much at all, I
>>>>>>would have realized that 'i/3' actually becomes a fixed point
>>>>>>multipl y by a reciprocal. no such reasoning was used in this case.
>>>>>>>
>>>>>>this was a trivial and obvious mistake is all.
>>>>>A trivial mistake that does not get made if you code what you want to
>>>>>express instead of trying to use tricks. That is part of the point.
>>>>'want to express'?...
>>>>>
>>>>this implies certain things, ie, that what I would want to express is
>>>>different from the code I would write to express it.
>>>Shift is for moving bits, divide is for scaling. Otherwise shift would
>>>work on floating point and would have behaviour defined by the C
>>>standard for negative numbers (it leaves it for the implementation to
>>>define the result of right shifting a negative number).
>>ok, makes sense.

>So will you move to the less error prone system then?
>>

>
I write whatever I write really.

Obviously.

in the past, I have never really seen any major problem with it.
>
if there were some problem, as I percieve it, then I probably would have
changed it long ago (before writing many hundreds of kloc using these kind
of conventions).

You not perceiving it does not mean it is not there.

>>>>do you ask me, if my grammar is unusual, if it is because I am not
>>>>writing what I am meaning to express?...
>>>>>
>>>>it is a similar question IMO...
>>>No, it is a question of using the wrong word. One that in some
>>>situations happens to be similar, but in many situations means something
>>>completely different.
>>the situations are different though.
>>as noted above, an integer and a float are conceptually different.
>>if I am speaking to someone do I count in floats? no, I count in
>>integers...

>I measure sizes in all sorts of different systems not all of which are
>integers.

>
lengths are reals, often.
>
sizes of arrays are not.

Decreasing the size of a malloced block by 42% is no different to
decreasing it by 50%. Yet one of them cannot easily be expressed as a shift.

counting is not.
>
we don't say '3.85 apples' because one of them is small, or '4.25' because
one is large...
the count is 4 apples.

No, but when someone cuts one of them in half and takes it away I would
say you have 3.5 apples.

>>>>>Whatever the reason for you learning to use such tricks it is well
>>>>>past time you learned not to use them excpet where it is proved that
>>>>>you need to.
>>>>>>
>>>>'tricks'?.. .
>>>Yes, it is a trick.
>>>>
>>>>shifts are a basic operator, I don't see why they would be viewed as
>>>>any kind of trick...
>>>The shift operator is a basic operator for moving bits, using it to
>>>divide is a trick and one that does not work in all situations.
>>it works on integers, integers are the context and the situation.
>>sizes are generally not negative either.

>They are sometimes.
>If a spec says a number is in bits 3 to 7 then getting it to the correct
>place is shifting.

>
I do this often as well.
for example, I have a good deal of packed-integer based types which I modify
via masks and shifts...

Same here historically, and it is a perfectly reasonable use of shifting.

>>there is no problem as I see it.

>I thought you admitted to an error that would not be made if using simple
>division. For one value you certainly suggested something more complex
>than simple division.

>
yes, this was a faulty thought, something I would have likely noticed and
fixed later for looking stupid...
>
I think it was because I was thinking of percentages, and this is the
typical way I manipulate things via percentages.
>
'17% of i' ='(i*17)/100'.
>
"i's percentage of j" '((i*100)/j)'.

You also suggested using multiple shifts and addition which is just
asking for errors and maintenance difficulty with very little chance of
a corresponding benefit.

>>>>do we call pointers and casts tricks as well?... typical code is
>>>>riddled with the things, nothing sinister there...
>>>Code riddled with casts probably is bad.
>>>>
>>>Code using a lot of shifts for shifting bits, NOT for division, could be
>>>good.
>>ok, but then one has to differentiate: when is the concept shifting bits
>>and when is it division?...
>>this is a subjective matter.

>I honestly cannot conceive of why one would consider shifting to be the
>natural way of scaling a value. Would you convert from inches to
>centimetres by shifting? Would you talk about doubling your salary or
>shifting it one bit to the left? Would you tell someone that they you have
>doubled the storage capacity of a disk array or shifted it one bit to the
>left? Or that the free space has been shifted one bit to the right instead
>of halved?

>
would probably not say it as such, but mentally I often use shifting in
performing calculations, as I find it easier than multiplication or
division.

I would say you are very unusual then since most people probably do not
know what a right shift is, and I suspect that most people who do
developed their thinking habits before learning what one is and so still
use multiplication/division.

>Changing the size of a buffer is NOT linked to the representation of the
>size, shifting is.

>
a buffer's size, however, is naturally constrained to being a positive
integer.

It is not, however, constrained to changing size by powers of 2.
Changing the size my 17% is also easy.

>>>>now, does one think in terms of arithmetic ops or in terms of bitwise
>>>>ops?...
>>>No. However a shift works in terms of bits, not in terms of arithmetic.
>>but on integers, bit ops are arithmetic...

>Nope. Right shift is a logical shift on some processors *not* arithmetic.
>If anyone ever builds a trinary machine then the shift operation procided
>by the processor will *not* be multiply/divide by 2. On a machine using
>BCD it isn't either, and BCD has been used for representing integer
>values.

>
maybe...
>
however, I reason, almost none of my crap is ever likely to be run on
something non-x86-based, much less something so far reachingly different,
which I would unlikely even consider coding for, assuming I ever even
encountered such a beast...

It does, however, show that you are thinking of manipulating the
representation rather than the fundamental concept.

>>makes nearly as much sense in conversation as it would in C.
>>we ask someone 'what is 12 and 7?' they say '8'...

>I can't see what point you are trying to make, unless it is why you should
>*not* use a shift for scaling.

>
the operations make sense to humans as well, if they know them...

Most people are more familiar with division than shift.

>>>>does one do their everyday arithmetic (internally) in decimal or in
>>>>hex?...
>>>>>
>>>>if we read something do we see the text, hear words, or see imagery?...
>>>Several of the things above are reasons for using divide rather than
>>>shift.
>>if one is confused as to whether not they are dealing with an integer...

>You still keep forgetting that it only works for half the integer types C
>provides, a sure sign in my opinion that you should stay well away from
>the shift operator in C.

>
was never saying it provably worked on negative integers.
however, it does work in what compilers I am fammiliar with.

Even in this post you keep referring to integers where you mean positive
integers. Use division and you don't have to worry about it being
incorrect for approximately half of the range of many integer types.

>You are confused about values and specific representations . Binary is not
>the only representation for numbers, it just happens to be the current
>vogue in computing.

>
theoretical argument, maybe, but IMO of little practical concern. I don't
think binary will go away anytime soon, as doing so would break much of the
software in existence at this point, and assuming such a change occures, it
will not matter since the mass of software would have been being
rewritten/replaced anyways.
>
I say though, not only is it valid for computers, but also humans...

Most humans do not think about shifting most of the time because most
humans when they think about a representation do not think in binary
most of the time.

>>what if I meant to grab an apple but instead grabbed a potatoe and
>>proceeded to eat it as said apple. people would look oddly, and then
>>maybe ones' stomach gets irritated from the raw potatoe...
>>>
>>so, casually eating an object raw is valid for an apple but not for said
>>potatoe.
>>likewise, we put potatoes in soup but not apples.
>>>
>>same difference really...

>All valid analogies for why you should be using division for scaling not
>shifting.
>>
><snip philosophy ramblings that seem to have no bearing on the matter at
>hand>
>>

>>>>this kind of issue has not come up in any time in recent memory...
>>>The issue of you making a mistake that you would not have done had you
>>>stuck to doing simple integer division is a good reason for using
>>>integer division.
>>potentially , but this makes an assumption about ones' thought process.
>>if one always types shifts, one thinks shifts, one does not think
>>division unless one were first thinking of division, which I assert that
>>I was not (which is why I think I missed such an obvious answer).

>So if someone tells you to increase a buffer by 81% you would think in
>terms of shifts?

>
naturally, I wouild have thought in one of the options I originally provided
'((i*81)/100)'.
why: because this value, as it so happens, does not have an integer
reciprocal.

It is no different in concept that 50% yet you use a different message
because shifting does not work easily. So it is simpler to always use
division, or multiplication and division than shifting.

>>>>so, one thinks in hex and writes in decimal, or vice versa, not usually
>>>>that important.
>>>>and, if one happens to be thinking in hex right, then a shift is more
>>>>intuitive than a divide.
>>>What do you get if you right shift -1? On some machines it will be 32767
>>>on others it will be -1. Does that sound like division to you?
>>different context.
>>>
>>one machine is probably an x86 in real mode with an int being 16 bits and
>>using shr.
>>the other is probably using sar.

>Nope, one machine is not an x86 and does not have an arithmetic shift at
>all.

>
ok, abstraction failing, it uses a 16 bit int.

So do compilers for the old 8086. I could have picked 2^31-1, but I
don't know the decimal representation of that by heart.

>>>>does one think of the money in their wallet as 300 or 0x12C?...
>>>>does one think in british or metric units?...
>>>>>
>>>>or does one use whatever system happens to seem more natural at that
>>>>instant?. ..
>>>Not relevant since a shift is not a different representation for
>>>division, it is a different operation.
>>it is an operation relevant to a situation, that situation being positive
>>integers...

>So when you have spent half your money do you think that you have shifted
>your resources one bit to the right?

>
very often, this is how I reason about some things.

You are IMHO unusual then.

>>I was not claiming it was also sane for floats or for negatives.

>Why? They are just numbers. In any case, you keep referring to integers
>rather than unsigned integers, so either you are repeatedly making a
>mistake and therefore showing why you should not be using shift you you
>are being sloppy in a way that leads to mistakes thus showing why using
>shift is inadvisable.

>
'unsigned integer' is longer to type, however in context I repeatedly
indicate that the numbers are positive, an indication that, whether the
storage is an integer or unsigned integer, the value is constrained to be
positive.
>
'23>>1' is '11' regardless of it being an int or uint.

x/2 is approximately half the value regardless of type.

>>>>up to them really. it only matters that when someone asks that they
>>>>give the right number, and when they read that they don't get
>>>>confused. ..
>>>>>
>>>>one typically doesn't know the magic going on even in ones' own head...
>>>Code is written for other people, not just the original author or the
>>>compiler.
>>maybe.
>>if other people ever actually read said code.

>You were advising on how someone else should do things, therefore someone
>other than you *will* see the code.

>
well, this is usenet, not ones' codebase.

Yes, so in examples it is better to show the conventional way to do things.

>>>>>>4/3 is a natural growth curve. something around this ratio should
>>>>>>presumabl y work good as a general mean case.
>>>>>Exponentia l is also a natural growth curve, if you don't believe me
>>>>>check how populations grow in nature, for at least some it is
>>>>>exponentia l until a crash.
>>>>when applied recursively, this is exponential...
>>>Linear is another natural growth curve.
>>except that linear is not a curve...

>Check the definition of a curve in maths and you will find that it *is* a
>curve. You will also find plenty of other growth curves in nature if you
>look.
>>

>
x^2 is a curve.
2^x is a curve.
x^0.5 is a curve.
>
x is not, it is linear, and thus not a curve.

See my previous comment. A straight line *is* a curve, just the special
case with 0 curvature. Ask any mathematician.

<snip>

>>and, for the previous topic:
>>it is by some odd convention that when we see a division by undivisible
>>integers that we realize that it has a non-integer output.

>Not if you know C you don't. Or Pascal. Or Modula 2. Or assembler. If you
>see integer division you expect an integer result because you know that
>when working in integers you are working in integers.

>
I was talking about fractions or rationals here.
>
humans have a convention that division of 2 integers leads to a non-integer
rather than an integer, and that computers do not is a difference. it shows
that integers are not numbers in a strictly traditional sense, because the
behavior is different.

Actually, humans have to be taught that and integer arithmetic *is* a
traditional form of arithmetic that pre-dates computers.

>>I guess it is also by similar convention that we realize that negative
>>even roots are imaginary and that non-integral exponents of negative
>>bases are complex...

>All completely irrelevant to the point. Why use something dependant on
>*representatio n* when there is a more natural operator for scaling, i.e.
>something that does not depend on representation.

>
representation is value, and implementation is definition...

No, representation is a way of representing a value. The number of
apples I have does not change depending on whether I say I have 10
applies or 8375 apples.

>>>--
>>>Flash Gordon

>Please don't quote signatures, the bit typically after a "-- ", unless you
>are commenting on them.
>--
>Flash Gordon

Did you not read the above? YOU SHOULD NOT QUOTE SIGNATURES.
--
Flash Gordon