/* Generate a texture from the population count of the coordinates.
 *
 * This was inspired by looking at the Thue-Morse sequence as a
 * texture, which is the *parity* of the sequence index, which is to
 * say the least significant bit of the population count.  So I
 * thought I’d see what the whole population count looked like.
 *
 * You can find various tricks for efficient software computation of
 * population count in, say, Hacker’s Delight, but due to expanding
 * silicon resources, dark silicon, and NSA requirements, nearly all
 * modern CPUs have a population-count instruction which is faster
 * than the software tricks.  GCC exposes this functionality via the
 * intrinsic __builtin_popcount.  And it falls back to the software
 * tricks if you don’t compile it for a CPU with a popcnt instruction:
 *
 * 0000000000400940 <__popcountdi2>:
 *   400940:	48 89 fa             	mov    %rdi,%rdx
 *   400943:	48 b8 55 55 55 55 55 	movabs $0x5555555555555555,%rax
 *   40094a:	55 55 55 
 *   40094d:	48 d1 ea             	shr    %rdx
 *   400950:	48 21 d0             	and    %rdx,%rax
 *   400953:	48 ba 33 33 33 33 33 	movabs $0x3333333333333333,%rdx
 *   40095a:	33 33 33 
 *   40095d:	48 29 c7             	sub    %rax,%rdi
 *   400960:	48 89 f8             	mov    %rdi,%rax
 *   400963:	48 c1 ef 02          	shr    $0x2,%rdi
 * ...
 *
 * But with the appropriate -m flag, it just generates the SSE popcnt
 * instruction:
 *
 * 00000000004005d6 <popcnt>:
 *   4005d6:	55                   	push   %rbp
 *   4005d7:	48 89 e5             	mov    %rsp,%rbp
 *   4005da:	89 7d fc             	mov    %edi,-0x4(%rbp)
 *   4005dd:	31 c0                	xor    %eax,%eax
 *   4005df:	f3 0f b8 45 fc       	popcnt -0x4(%rbp),%eax
 *   4005e4:	5d                   	pop    %rbp
 *   4005e5:	c3                   	retq   
 */

#include "ppmp6.h"

enum { ww = 512, hh = 512 };
ppm_p6_color image[hh][ww];

static inline int
popcnt(unsigned x)
{
  return __builtin_popcount(x);
}

int main(int argc, char **argv)
{
  for (int y = 0; y < hh; y++) {
    for (int x = 0; x < ww; x++) {
      int i = popcnt(x) + popcnt(y);
      ppm_p6_color color = { .r = .06*i, .g = .03*i, .b = .03*i };
      image[y][x] = color;
    }
  }

  ppm_p6_output_image(image[0], ww, hh);
  return 0;
}