Dynamically resizing a buffer

F

Flash Gordon

santosh wrote, On 27/08/07 14:48:
I caught it in several other places :)

I would second your motion, but I suspect that is against the rules.
Poor Flash,

Actually, I'm not that badly paid ;-)
unfortunately, grammar checkers aren't useful yet!

Several years ago I used one that was IMHO very good. However, I've not
seen any others that worked as well in all the years since. The decent
one was in a version of WordPerfect.
 
F

Flash Gordon

CBFalconer wrote, On 23/08/07 21:55:
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.

You are correct, but only for positive values. Since it does *not* work
as an arithmetic division for all values the operator is valid for I
stand by my assertion.
 
J

Joe Wright

CBFalconer said:
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. 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
Shifting this right should result in
11111100 -4 again
instead of
01111100 124

All of my C implementations over the years preserve the sign on
right-shifting a signed integer. Are there any that don't?
 
R

Richard Tobin

All of my C implementations over the years preserve the sign on
right-shifting a signed integer. Are there any that don't?

In the 1980s I used to maintain code that had an (automatically
generated) #define for a preprocessor variable "RtShArith" which
indicated whether right shifts of integers were arithmetic
(i.e. sign-preserving) or logical. I can no longer which it was, but
certainly some C implementation we used didn't preserve the sign.

-- Richard
 
L

lawrence.jones

Joe Wright said:
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
 
C

CBFalconer

Joe said:
CBFalconer wrote:
.... snip ...


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.

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.
 
R

Richard Bos

Joe Wright said:
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
 
J

Joe Wright

CBFalconer said:
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.
 
C

CBFalconer

Joe said:
.... 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.
 
F

Flash Gordon

cr88192 wrote, On 25/08/07 05:00:
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.



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.
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.
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.
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.
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.
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.
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.
the operations make sense to humans as well, if they know them...

Most people are more familiar with division than shift.
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.
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.
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.
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.
very often, this is how I reason about some things.

You are IMHO unusual then.
'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.
well, this is usenet, not ones' codebase.

Yes, so in examples it is better to show the conventional way to do things.
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.

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.
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.

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top