[Tutor] Malloc, bitwise operations and other nasties

[David Ascher]

On Tue, 9 Mar 1999, Art Siegel wrote:

> The following is a code snippet from OpenGL demo code I am trying to
> port to Python.

> /* Create a single component texture map */ 
> GLfloat * 
> make_texture(int maxs, int maxt) 
> { 
> int s, t; 
> static GLfloat *texture; 
> texture = (GLfloat *) malloc(maxs * maxt * sizeof(GLfloat)); 
> for (t = 0; t < maxt; t++) { 
> for (s = 0; s < maxs; s++) { 
> texture[s + maxs * t] = ((s >> 4) & 0x1) ^ ((t >> 4) & 0x1); 
> } 
> } 
> return texture; 
> }
> The code creates a checkerboard texture, which gets mapped to an object.
> Between the malloc call (something to do with memory, I know) and the bitwise operators, I am lost.
> I certainly can't see how this becomes a texturemap.
> If I saw the code in Pythonese, I couldl probably begin to understand it. 
> Any help is appreciated.

This is a great example of why C is ugly =)

malloc creates an array of unitialized bytes.  A close equivalent to the
above code in Python would be

texture = [0.0]*(maxs*maxt)
for t in range (maxt):
  for s in range(maxs):
    texture[s + maxs * t] = ((s >> 4) & 0x1) ^ ((t >> 4) & 0x1); 


If you try it with maxs and maxt set to 20, you'll see the 'scan lines':

>>> maxt = maxs = 20
>>> texture = [0.0]*(maxs*maxt)
>>> for t in range (maxt):
...   for s in range(maxs):
...     texture[s + maxs * t] = ((s >> 4) & 0x1) ^ ((t >> 4) & 0x1);
...
>>> print texture
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
1, 1, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1,
 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1,
1, 1, 1 , 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 0, 0, 0, 0]

However, looking at it like that makes it a bit hard to see how it works.
One could recode it as:

>>> texture = []
>>> for t in range (maxt):
...    line = []              # note we're using lists of lists
...    texture.append(line)   # to make the 'lines'
...    for s in range(maxs):
...       line.append(((s >> 4) & 0x1) ^ ((t >> 4) & 0x1))
...
>>> texture
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1], 
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0], 
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0]
]

(this looks if you try like the corner of a checkerboard)

How does it work?  The key is clearly the 

  ((s >> 4) & 0x1) ^ ((t >> 4) & 0x1);

s >> 4 is the value of s, shifted to the right by four bits.  When AND'ed
with 1, that tests whether the bit four bits from the right in s is on or
not.  When OR'ed with the equivalent for t, that will be 1 if either the
fourth bit in s or the fourth bit in t are on (or both).  Which means that
columns 16 through 31 and rows 16 through 31 will be "on", and columns 0
through 15 and rows 0 through 15 will be 'off' (with that pattern repeated
ad infinitum).  So the "4" in the right-shift operation determines the
"coarseness" of the texture.  The bit at the '4th position from the right'
is the bit corresponding to 2 to the fourth, or 16.  So in this case the
checkerboard is 16-off, 16-on.  If you make it 5, you'll get 32x32
checkerboards, etc.  

[I'm not happy about this discussion of bit-shifting -- anyone got better
 words to describe binary representations? -- say, Tim, where's that
 module of yours again?]

[To use this lists of lists in PyOpenGL you'll have to flatten it first,
 as per our discussion on the PyOpenGL list, until the next release]

Make sense?

--david