why const-qualify a pointer?

[BartC]

Or you can replace the function with "return 1;"! You've lost track of
the purpose. If the image is cleared, all points will appear connected.

The input image A contains the original picture. The auxiliary local image B
is just a mask indicating what would be the flooded areas of A.

(Malcolm has since said that A is a 2-level image anyway - presumably what
he meant by 'binary-image'. These tend to be compact so a straight copy to a
local image seems simplest - once you've first checked the two points are
the same colour.

However, I also vaguely remember that he implements these using one
char per pixel. That means there are 254 possible values to pick for the
flood-fill, that do not clash with the colours of the image. Which I suppose
is similar to my idea, but using 7 spare bits that already permanently
exist, instead of the one temporary extra bit I proposed.)

 

[Ben Bacarisse]

The input image A contains the original picture. The auxiliary local image B
is just a mask indicating what would be the flooded areas of A.

You stated that the auxiliary image will be zeros, didn't you? If it's
clear, a flood-fill fills all points (or none in the degenerate case of
filling with zero).

<snip>

 

[BartC]

You stated that the auxiliary image will be zeros, didn't you? If it's
clear, a flood-fill fills all points (or none in the degenerate case of
filling with zero).

I obviously didn't make myself clear. The flood-fill routine needs to be
modified to work with both images, reading from A, and reading/writing
from/to B. Effectively B extends the pixel-width of A by one bit.

So if A was 8-bit greyscale/palette with a colour range of 0 to 255, then
the following special get/setpixel routines can take care of the logic, with
a new colour range of 0 to 256. It assumes routines exist for ordinary
get/setpixel:

#define flood_fill_colour 256

/* A, B are images; x, y are ints: */

int getpixel_ff (const A, B, x, y) {
if (getpixel(B, x, y)==1)
return flood_fill_colour;
return getpixel(A, x, y);
}

void setpixel_ff (const A, B, x, y, colour) {
if (colour==flood_fill_colour)
setpixel(B, x, y, 1);
else /* this branch may not be needed */
setpixel(B, x, y, 0); /* Assume A(x,y) is already set to colour */

}

 

[Ben Bacarisse]

I obviously didn't make myself clear. The flood-fill routine needs to be
modified to work with both images, reading from A, and reading/writing
from/to B. Effectively B extends the pixel-width of A by one bit.

I see. You are flood-filling a composite image with, as you say, one
more pixel available.

<snip detail>

 

[Martin Shobe]

You stated that the auxiliary image will be zeros, didn't you? If it's
clear, a flood-fill fills all points (or none in the degenerate case of
filling with zero).

<snip>

The auxiliary image isn't directly flood-filled. It's just used to mark
which pixels have been visited during the flood-fill so you don't have
to change the original image.

E.g.

Image Auxiliary
11101112 00000000
10110100 00000000
11100102 00000000
01111111 00000000

After fill
Image Auxiliary
11101112 11101110
10110100 10110100
11100102 11100100
01111111 01111111

Martin Shobe

 

[Seebs]

A binary image has set/unset pixels. So passing a value other than 1 or 0
results in undefined behaviour.

That doesn't seem to address things. Come up with any plausible set of 0s
and 1s, start at some point changing all the connected 0s to 1s, then change
all the connected 1s to 0s, and you will likely have flipped a few bits to
0s that should have stayed 1s.

-s

 

[Philip Lantz]

That doesn't seem to address things. Come up with any plausible set of 0s
and 1s, start at some point changing all the connected 0s to 1s, then change
all the connected 1s to 0s, and you will likely have flipped a few bits to
0s that should have stayed 1s.

Yeah, that's pretty obvious. Which is why you might have recognized that
it is not what he was suggesting.

Communication usually works better if one assumes the other person isn't
talking nonsense. (If he actually is, you'll figure it out soon enough.)
This guideline seems to be broken more often in this newsgroup than in
any other place I encounter.

While he didn't explain it very transparently, it was clear that he was
postulating a bitmap with 8-bit pixels, but where the only legal values
were 0 and 1. You could reasonably question whether that's a reasonable
way to represent bitmaps, but I don't think it's nonsense.

 

[Jorgen Grahn]

But consider this.

bool connected(const unsigned char *binaryimage, int width, int height, int x1, int y1, int x2, int y2)

it's naturally const. We want to detect whether x1,y1 and x2,y2 are connected
by a path of set pixels. We don't want to modify the data.

[snip solution which involves modify-and-restore]

Sure, there /are/ cases where you intend to say 'foo(const bar*)' but
cannot. Those are rare exceptions, though!

/Jorgen

 

[Seebs]

Yeah, that's pretty obvious. Which is why you might have recognized that
it is not what he was suggesting.

That's a good point -- Miller's Law.

Communication usually works better if one assumes the other person isn't
talking nonsense. (If he actually is, you'll figure it out soon enough.)
This guideline seems to be broken more often in this newsgroup than in
any other place I encounter.

That can be a really useful technique, but trying too hard to come up with
a sensible thing someone might have intended can result in miscommunications
too. Although it would almost certainly have been more useful for me to
consider more carefully that I might be misunderstanding.

While he didn't explain it very transparently, it was clear that he was
postulating a bitmap with 8-bit pixels, but where the only legal values
were 0 and 1. You could reasonably question whether that's a reasonable
way to represent bitmaps, but I don't think it's nonsense.

It seems a little surprising, but I guess it does make sense -- so you'd be
filling with a value which wasn't valid, and then reverting that. I guess
the reason I didn't pick that interpretation is that it requires an assumption
that I didn't think was clearly stated, and that makes it seem like a poor
example of a generally-useful tactic.

-s

 

[Malcolm McLean]

It seems a little surprising, but I guess it does make sense -- so you'd be
filling with a value which wasn't valid, and then reverting that. I guess
the reason I didn't pick that interpretation is that it requires an assumption
that I didn't think was clearly stated, and that makes it seem like a poor
example of a generally-useful tactic.

I'm not sure it's really good programming, as mistakes could introduce difficult
to find bugs. But memory allocation is also a pain.
I use one byte per pixel for binary images, mainly for simplicity. Whilst you can compress the data into a bit per pixel, it means accessing everything
through macros. Also, most binary images have local coherence. So bit packing
isn't the best way to compress them. I've got a compress utility if storage
is a problem.

 

[Edward A. Falk]

The advantage to const-qualifying a pointer (if there is such an
advantage) is the same as for const-qualifying anything else. It
documents your belief that the thing so-qualified is not supposed to be
changed, in a way that mandates a diagnostic message if you make the
mistake of writing code that might try to change it.

Exactly. Here's a concrete example from a device driver I once wrote:
a number of functions were called with a shift width as an argument.
From the shift width, I computed a mask. It was very important to remember
to recompute the mask if the shift width changed. So as a precaution,
I declared the shift width to be const everywhere it appeared, along
with a comment explaining why.

In this way, any attempt by another developer to change the shift width
would result in a compiler warning which would lead the developer to
the comment explaining that if you're going to change the shift, you
have to change the mask too.

Other than that, a const modifier can theoretically allow the compiler to
make certain optimizations, although I expect any decent modern compiler
to figure that out by itself.

 

[Edward A. Falk]

The basic issue: Some functions which take a pointer want to modify
the thing pointed to. Some don't. Sometimes, I have a thing which I wouldn't
mind having the code modify, sometimes, I really don't want it modifying
the thing. If I don't have a 100% perfect memory of which functions are
which, I am likely to occasionally pass a pointer to data I don't want
modified into a function which will modify data.

Fun fact: FORTRAN passes all values by reference. If you passed a constant
to a function that would modify its argument, you could wind up changing
the value of the constant itself. Those bugs were a *lot* of fun to track
down.

 

[Edward A. Falk]

But consider this.

bool connected(const unsigned char *binaryimage, int width, int height, int x1, int y1, int x2, int y2)

[more efficient to implement if you change the data, then change it back,
rather than to copy it and change the copy.]

That's why you're allowed to cast away const.

(But if I had to review your code, all the hair on the back of my neck
would stand up, and I'd be in your cubicle making you prove to me that
this wouldn't fail, even if used in a threaded environment.)

 

[Les Cargill]

Exactly. Here's a concrete example from a device driver I once wrote:
a number of functions were called with a shift width as an argument.
From the shift width, I computed a mask. It was very important to remember
to recompute the mask if the shift width changed. So as a precaution,
I declared the shift width to be const everywhere it appeared, along
with a comment explaining why.

It's ambiguous from your post, but you might have been able to calculate
the mask as well. Then it's all moot.

In this way, any attempt by another developer to change the shift width
would result in a compiler warning which would lead the developer to
the comment explaining that if you're going to change the shift, you
have to change the mask too.

Other than that, a const modifier can theoretically allow the compiler to
make certain optimizations, although I expect any decent modern compiler
to figure that out by itself.

That is actually less important than constraining the l-values of
some things.

 

[glen herrmannsfeldt]

(snip)

Fun fact: FORTRAN passes all values by reference. If you passed a constant
to a function that would modify its argument, you could wind up changing
the value of the constant itself. Those bugs were a *lot* of fun to track
down.

Traditionally Fortran compilers had the choice of pass by reference
or pass by value result. Proper programs can't tell the difference.

Fortran now has the VALUE attribute to allow for pass by value, often
used when calling C routines. There is also INTENT(IN) and INTENT(OUT)
to describe what you intend to do with the argument.

-- glen

 

[Malcolm McLean]

Other than that, a const modifier can theoretically allow the compiler to
make certain optimizations, although I expect any decent modern compiler
to figure that out by itself.

Pointer aliasing is very difficult for compilers to work out. const qualifying
means that the compiler does have to worry that the const pointer items will
be written to, which effectively means it can regard them as "no alias".

 

[ais523]

Pointer aliasing is very difficult for compilers to work out. const qualifying
means that the compiler does have to worry that the const pointer items will
be written to, which effectively means it can regard them as "no alias".

I don't think so. Imagine code like this:

int f(int *x, const int *y)
{
*x += *y;
*x -= *y;
return *x;
}

I don't believe that code can be correctly optimized into

int f(int *x, const int *y)
{
(void)y;
*x = 0;
return 0;
}

because of the chance that x and y point to the same memory location,
and at least, the compilers I tested will refuse to perform that
"optimisation" as given, although of course that's not a perfect test.
(Checking what the Standard said would be better, but I find the
relevant part of the Standard very hard to follow.)

(The "restrict" keyword was invented in C99 partly for this sort of
reason. The compilers I tested will optimize the first function into
the same code that would be produced by the second if I add "restrict"s
to the arguments.)

 

[Malcolm McLean]

Malcolm McLean wrote:





I don't think so. Imagine code like this:

int f(int *x,
const int *y)
{

*x += *y;

*x -= *y;

return *x;

}



I don't believe that code can be correctly optimized into



int f(int *x, const int *y)

{

(void)y;

*x = 0;

return 0;

}



because of the chance that x and y point to the same memory location,
and at least, the compilers I tested will refuse to perform that
"optimisation" as given, although of course that's not a perfect test.
(Checking what the Standard said would be better, but I find the
relevant part of the Standard very hard to follow.)

Assuming aliasing is allowed, the function returns *x if x and y are different
0 if they are aliases.
The optimisation would probably be register temp = *y; x += temp; *x -= temp,
so that *x has the right value between sequence points. (This isn't
absolutely required, but compilers tend to assume that this is what the
programmer wants, or he'd have written *x = *x + *y - *y

 

[ais523]

Surely not, because that "optimization" is wrong in any case. If x and y
were not aliased, the compiled could do

int f(int *x, const int *y) {
return *x;
}

Err yes. That's what I meant, although it's not at all what I said.
Sorry about the confusion.

 

[Tim Rentsch]

Pointer aliasing is very difficult for compilers to work out.
const qualifying means that the compiler does have to worry that
the const pointer items will be written to, which effectively
means it can regard them as "no alias".

Presumably this was meant to say "the compiler does _not_ have to
worry that the const pointer items will be written to". That's
wrong. To give a specific example

int x;

int
foo( const int *p ){
x = *p + 1;
return *p;
}

the function foo() may not be transformed to act like the
function bas()

int
bas( const int *p ){
int r = *p;
x = r + 1;
return r;
}

precisely because the assignment to 'x' may change the
value of '*p'.