|
|
Home » Extra libraries, Code snippets, applications etc. » C++ language problems and code snippets » Time for little quiz!
|
Re: Time for little quiz! [message #2229 is a reply to message #2219] |
Tue, 04 April 2006 19:12 |
|
luzr wrote on Tue, 04 April 2006 08:02 | What is this construct supposed to do (and why):
void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
delete new sPalMaker(s, count, palette, ncolors);
}
Mirek
|
It look very interesting.. but I have no idea what this construction is supposed to do..
I would use delete new if I'd like to create object on heap (but what for?) and to end object live as soon as possible.
The next reason that came to my mind is you don't have to name the object..
But why delete new sPalMaker.. is better than simply
{
sPalMaker pm(s, count, palette, ncolors);
} ?
PS: Maybe this is stupid, but will compiler ignore creating the object if it is not created on heap because the pm isn't used further?
[Updated on: Tue, 04 April 2006 19:16] Report message to a moderator
|
|
|
Re: Time for little quiz! [message #2232 is a reply to message #2219] |
Tue, 04 April 2006 20:04 |
|
fudadmin
Messages: 1321 Registered: November 2005 Location: Kaunas, Lithuania
|
Ultimate Contributor Administrator |
|
|
luzr wrote on Tue, 04 April 2006 13:02 | What is this construct supposed to do (and why):
void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
delete new sPalMaker(s, count, palette, ncolors);
}
Mirek
|
I'm lazy to think and test but my guess are some keywords:
some kind of clever pointers and/or references, auto counting ... memory management, deletion on creation when something related is not deleted but made free for shared use...
|
|
|
Re: Time for little quiz! [message #2233 is a reply to message #2232] |
Tue, 04 April 2006 20:36 |
|
mirek
Messages: 14105 Registered: November 2005
|
Ultimate Member |
|
|
Well, sorry for teasing, it is just an interesting solution for simple problem:
sPalMaker is "procedural object", in fact, it is routine wrapped in the class instance. All relevant work is done in constructor.
Now the trouble is that sizeof(sPalMaker) > 65KB, something I do not like to put to the stack (otherwise solution you propose would be OK as well). So "delete new" does exactly what I want - offloads memory requirements to the heap.
Mirek
[Updated on: Wed, 05 April 2006 10:46] Report message to a moderator
|
|
|
|
Re: Time for little quiz! [message #2248 is a reply to message #2245] |
Wed, 05 April 2006 10:53 |
|
mirek
Messages: 14105 Registered: November 2005
|
Ultimate Member |
|
|
That would be much more code to write. In fact, there is a couple of methods in class, and class intance here is a sort of replacement of Pascal's embedded function/procedures.
BTW, as this is quite nice implementation of median cut palette algorithm, and I was trying quite hard to google some code for this, maybe placing it here will make further implementors search easier:
Median cut palette algorithm in C++:
struct sPalMaker {
int histogram[RASTER_MAP_R][RASTER_MAP_G][RASTER_MAP_B];
int colorcount;
struct Dim {
int l, h;
operator int() { return h - l; }
};
enum { G = 0, R = 1, B = 2 };
void Copy(Dim *d, Dim *s) { d[R] = s[R]; d[G] = s[G]; d[B] = s[B]; }
struct Box {
int volume;
int colorcount;
int population;
Dim dim[3];
int avg_r, avg_g, avg_b;
Dim& operator[](int i) { return dim[i]; }
};
void Update(Box& box, int ii);
sPalMaker(const RGBA *s, int count, RGBA *palette, int ncolors);
};
void sPalMaker::Update(Box& x, int ii)
{
x.colorcount = 0;
x.population = 0;
int a[3][RASTER_MAP_MAX];
ZeroArray(a[R]);
ZeroArray(a[G]);
ZeroArray(a[B]);
x.avg_r = x.avg_g = x.avg_b = 0;
for(int r = x[R].l; r < x[R].h; r++)
for(int g = x[G].l; g < x[G].h; g++)
for(int b = x[B].l; b < x[B].h; b++) {
int q = histogram[r][g][b];
a[R][r] += q;
a[G][g] += q;
a[B][b] += q;
x.avg_r += q * r;
x.avg_g += q * g;
x.avg_b += q * b;
x.colorcount += (-q >> 31) & 1;
x.population += q;
}
for(int i = 0; i < 3; i++) {
Dim& d = x[i];
while(d.l < d.h && a[i][d.l] == 0)
d.l++;
while(d.h > d.l && a[i][d.h - 1] == 0)
d.h--;
}
x.volume = x[R] * x[G] * x[B];
}
static byte sRc(int avg, int pop, int div)
{
return Saturate255(255 * (avg + (pop >> 1)) / pop / (div - 1));
}
sPalMaker::sPalMaker(const RGBA *s, int count, RGBA *palette, int ncolors)
{
ASSERT(ncolors <= 256);
ZeroArray(histogram);
for(const RGBA *e = s + count; s < e; s++)
histogram[s->r >> RASTER_SHIFT_R][s->g >> RASTER_SHIFT_G][s->b >> RASTER_SHIFT_B]++;
Buffer<Box> box(256);
box[0][R].l = 0;
box[0][R].h = RASTER_MAP_R;
box[0][G].l = 0;
box[0][G].h = RASTER_MAP_G;
box[0][B].l = 0;
box[0][B].h = RASTER_MAP_B;
Update(box[0], 0);
if(box[0].population == 0)
return;
colorcount = box[0].colorcount;
count = 1;
int method = 1;
while(count < ncolors) {
int ii = -1;
int maxv = 0;
if(2 * count > ncolors)
method = 1;
for(int i = 0; i < count; i++) {
int v = method ? box[i].volume : box[i].colorcount;
if(box[i].colorcount > 1 && v > maxv) {
ii = i;
maxv = v;
}
}
if(ii < 0)
break;
Box& b = box[ii];
int ci = b[R] > b[G] ? b[B] > b[R] ? B : R : b[B] > b[G] ? B : G;
if(b[ci] == 1) {
if(method == 1)
break;
method = 1;
}
else {
int m = (b[ci].l + b[ci].h) >> 1;
Box& b1 = box[count];
b1 = b;
b[ci].h = m;
b1[ci].l = m;
Update(b, ii);
Update(b1, count++);
}
}
for(int i = 0; i < count; i++) {
RGBA& c = palette[i];
Box& x = box[i];
c.r = sRc(x.avg_r, x.population, RASTER_MAP_R);
c.g = sRc(x.avg_g, x.population, RASTER_MAP_G);
c.b = sRc(x.avg_b, x.population, RASTER_MAP_B);
c.a = 255;
}
}
void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
ASSERT(ncolors <= 256);
delete new sPalMaker(s, count, palette, ncolors);
}
|
|
|
|
|
Re: Time for little quiz! [message #2252 is a reply to message #2251] |
Wed, 05 April 2006 12:04 |
|
mirek
Messages: 14105 Registered: November 2005
|
Ultimate Member |
|
|
gprentice wrote on Wed, 05 April 2006 05:20 |
luzr wrote on Wed, 05 April 2006 20:54 | PS, note this nice gem as well:
x.colorcount += (-q >> 31) & 1;
Mirek
|
Do you feel like explaining?
I'm sure you know that right shift of a signed negative value has an implementation defined result and that int isn't always 32 bits and ... why would you write obscure code like this ???
Graeme
|
To avoid conditional jump in inner loop:
I need
if(q) colorcount++;
Now I know that q is positive number or zero. By negating positive number, you obviously get 1 in the highest bit. By negating zero, you get zero...
BTW, U++ guarantees int to be at least 32 bits (in other words, it requires it as well Also, right shift is implementation defined, however it guarantees that it is a shift... (I mean, what is implementation defined is content of high bits, but obviously, existing bits have to be shifted...)
On the similar theme:
inline byte Saturate255(int x) { return byte(~(x >> 24) & (x | (-(x >> 8) >> 24)) & 0xff); }
jump-less equivalent of min(max(x, 0), 255) (important in image processing).
Mirek
[Updated on: Wed, 05 April 2006 12:05] Report message to a moderator
|
|
|
Re: Time for little quiz! [message #2253 is a reply to message #2219] |
Wed, 05 April 2006 12:23 |
gprentice
Messages: 260 Registered: November 2005 Location: New Zealand
|
Experienced Member |
|
|
ok, well sorry to be dumb but ... why do you want to avoid the conditional jump. Why do you think x.colorcount += (-q >> 31) & 1; is going to be more efficient than if(q) colorcount++; (or x.colorcount += bool(q); )
The compiler could be smart enough to generate a test and jump instead of shifting 31 times anyway or doing something else ??
BTW - I was thinking of 64 bit machines (regarding 32 bit ints) - but compilers for 64 bit seem to have standardized on 32 bits for int still?
Graeme
[Updated on: Wed, 05 April 2006 12:24] Report message to a moderator
|
|
|
Re: Time for little quiz! [message #2254 is a reply to message #2229] |
Wed, 05 April 2006 12:31 |
gprentice
Messages: 260 Registered: November 2005 Location: New Zealand
|
Experienced Member |
|
|
unodgs wrote on Wed, 05 April 2006 05:12 |
luzr wrote on Tue, 04 April 2006 08:02 | What is this construct supposed to do (and why):
void CreatePalette(const RGBA *s, int count, RGBA *palette, int ncolors)
{
delete new sPalMaker(s, count, palette, ncolors);
}
Mirek
|
It look very interesting.. but I have no idea what this construction is supposed to do..
I would use delete new if I'd like to create object on heap (but what for?) and to end object live as soon as possible.
The next reason that came to my mind is you don't have to name the object..
But why delete new sPalMaker.. is better than simply
{
sPalMaker pm(s, count, palette, ncolors);
} ?
PS: Maybe this is stupid, but will compiler ignore creating the object if it is not created on heap because the pm isn't used further?
|
The compiler can ignore creating the pm object if it can determine that doing so makes no difference to the output (observable behaviour) of the program. There are situations where the compiler can elide (means ignore/not do) a call to a copy constructor even if the copy constructor has side effects (modifies a global variable or something) - the famous return value optimisation (RVO) being one - but apart from these, the compiler has to do what you tell it if it makes a difference to the output of the program.
Graeme
|
|
|
Re: Time for little quiz! [message #2255 is a reply to message #2253] |
Wed, 05 April 2006 13:14 |
|
mirek
Messages: 14105 Registered: November 2005
|
Ultimate Member |
|
|
gprentice wrote on Wed, 05 April 2006 06:23 | ok, well sorry to be dumb but ... why do you want to avoid the conditional jump. Why do you think x.colorcount += (-q >> 31) & 1; is going to be more efficient than if(q) colorcount++; (or x.colorcount += bool(q); )
|
Most likely on any CPU since Pentium I: Failed branch prediction causes pipline stall - that is at least 12 CPU cycles wasted (31 on Prescott). Also, jumps cannot be fed to more executional units - while arithmetic ops can be. It is very likely that modern CPU will be doing those colorcount ops in the same time as operations around.
BTW, shifting 31 times is 1 cycle on AMD and PIII/Core/Conroe CPUs (unfortunately, it is more pricey for Netburst, however failed branch prediction is still even more pricey there).
Quote: |
BTW - I was thinking of 64 bit machines (regarding 32 bit ints) - but compilers for 64 bit seem to have standardized on 32 bits for int still?
|
Yes, all major 64 bit CPUs today have 32bit ints. Well, to put it more straight, standard for all C compilers is to use 32 bit ints, other than that they support 8/16/32/64 integer quantities.
The reason is obvious - 32 bits is enough in most cases where integer quantity is to be used and 64 bit ints would eat much more space in data cache. BTW, AMD64 opcodes for 64 bit int operarations are 1 byte longer (they have "use 64 bits" prefix).
All that said, above jump-less technique would work with 64bit int as well.
Mirek
[Updated on: Wed, 05 April 2006 13:14] Report message to a moderator
|
|
|
|
|
|
|
|
|
|
|
Goto Forum:
Current Time: Fri Nov 01 00:18:05 CET 2024
Total time taken to generate the page: 0.02173 seconds
|
|
|