Bits and Pieces

[kingliveson]

Ben, I will give you another version:

Code: Select all

inline int MemberCount(long long Bits)
{
    int Count = 0;

    while (Bits != 0)
    {
        ++Count;
        Bits &= (Bits - 1);
    }

    return Count;
}
// COPYRIGHT 2011 Bo Persson

With VS2010 64-bit edition, this generates exactly the same instructions as the Crafty hand optimized assembler version.

Now, without copying any code, try to figure out how this works and write your own version.

Copyright problem solved!

Code: Select all

static inline int popcount_original(unsigned *buf, int n) {
  int cnt=0;
  unsigned v;
  while (n--) {
    v = *buf;
    while (v) {
      cnt++;
      v &= v-1;
    }
    buf++;
  }
  return cnt;
}

Unoptimized GCC generated:

Code: Select all

_MemberCount:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$24, %esp
	movl	8(%ebp), %eax
	movl	%eax, -24(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	$0, -4(%ebp)
	jmp	L8
L9:
	addl	$1, -4(%ebp)
	movl	-24(%ebp), %eax
	movl	-20(%ebp), %edx
	addl	$-1, %eax
	adcl	$-1, %edx
	andl	%eax, -24(%ebp)
	andl	%edx, -20(%ebp)
L8:
	movl	-24(%ebp), %eax
	movl	-20(%ebp), %edx
	orl	%edx, %eax
	testl	%eax, %eax
	jne	L9
	movl	-4(%ebp), %eax
	leave
	ret

Code: Select all

_popcount_original:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$16, %esp
	movl	$0, -8(%ebp)
	jmp	L12
L15:
	movl	8(%ebp), %eax
	movl	(%eax), %eax
	movl	%eax, -4(%ebp)
	jmp	L13
L14:
	addl	$1, -8(%ebp)
	movl	-4(%ebp), %eax
	subl	$1, %eax
	andl	%eax, -4(%ebp)
L13:
	cmpl	$0, -4(%ebp)
	jne	L14
	addl	$4, 8(%ebp)
L12:
	cmpl	$0, 12(%ebp)
	setne	%al
	subl	$1, 12(%ebp)
	testb	%al, %al
	jne	L15
	movl	-8(%ebp), %eax
	leave
	ret

[benstoker]

Ben, I will give you another version:

Code: Select all

inline int MemberCount(long long Bits)
{
    int Count = 0;

    while (Bits != 0)
    {
        ++Count;
        Bits &= (Bits - 1);
    }

    return Count;
}
// COPYRIGHT 2011 Bo Persson

With VS2010 64-bit edition, this generates exactly the same instructions as the Crafty hand optimized assembler version.

Now, without copying any code, try to figure out how this works and write your own version.

Copyright problem solved!

Code: Select all

static inline int popcount_original(unsigned *buf, int n) {
  int cnt=0;
  unsigned v;
  while (n--) {
    v = *buf;
    while (v) {
      cnt++;
      v &= v-1;
    }
    buf++;
  }
  return cnt;
}

Unoptimized GCC generated:

Code: Select all

_MemberCount:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$24, %esp
	movl	8(%ebp), %eax
	movl	%eax, -24(%ebp)
	movl	12(%ebp), %eax
	movl	%eax, -20(%ebp)
	movl	$0, -4(%ebp)
	jmp	L8
L9:
	addl	$1, -4(%ebp)
	movl	-24(%ebp), %eax
	movl	-20(%ebp), %edx
	addl	$-1, %eax
	adcl	$-1, %edx
	andl	%eax, -24(%ebp)
	andl	%edx, -20(%ebp)
L8:
	movl	-24(%ebp), %eax
	movl	-20(%ebp), %edx
	orl	%edx, %eax
	testl	%eax, %eax
	jne	L9
	movl	-4(%ebp), %eax
	leave
	ret

Code: Select all

_popcount_original:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$16, %esp
	movl	$0, -8(%ebp)
	jmp	L12
L15:
	movl	8(%ebp), %eax
	movl	(%eax), %eax
	movl	%eax, -4(%ebp)
	jmp	L13
L14:
	addl	$1, -8(%ebp)
	movl	-4(%ebp), %eax
	subl	$1, %eax
	andl	%eax, -4(%ebp)
L13:
	cmpl	$0, -4(%ebp)
	jne	L14
	addl	$4, 8(%ebp)
L12:
	cmpl	$0, 12(%ebp)
	setne	%al
	subl	$1, 12(%ebp)
	testb	%al, %al
	jne	L15
	movl	-8(%ebp), %eax
	leave
	ret

Do note that mine is the only original version, as it is named popcount_original.

[Gerd Isenberg]

Once again my head is ready to explode after a post from Gerd.

Oups.

Well-researched. I only knew for certain that it wasn't my idea and I was not interested in trying to claim credit...

Thanks Google. Actually the original quote is from Bit Twiddling Hacks by Sean Eron Anderson:

Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to me that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)"

For Ben. I have another variation on that theme

Code: Select all

int hammingWeight(Bitboard b) {
  int n;
  for (n=0; b; n++, b ^= b & -b);
  return n;
}

[benstoker]

one-input -> one-output is pretty clear and well-defined. The minute you reach one-input -> multiple possible outputs, you cross the line. But not before, IMHO. Note that this is a suggestion. NO one has adopted it as a rule or policy...

Is this correct, then?

1) If one-input-one-output function, then source code of this function can be copy/pasted into an original engine.

2) If one-input-MULTIPLE-possible-outputs function, then source code of this function cannot be copy/pasted into an original engine.

Application:

Process for designing new original chess engine to compete in ICGA:

a) Divide all Crafty functions into the 2 categories, one->one and one->many.

b) Write new chess engine that comprises copy/pasted source code of ALL of Crafty's one->one functions.

c) Write all the other one->many functions utilizing all the state-of-the-art chess engine heuristics ideas.

Voila! Original chess engine?

[hyatt]

one-input -> one-output is pretty clear and well-defined. The minute you reach one-input -> multiple possible outputs, you cross the line. But not before, IMHO. Note that this is a suggestion. NO one has adopted it as a rule or policy...

Is this correct, then?

1) If one-input-one-output function, then source code of this function can be copy/pasted into an original engine.

2) If one-input-MULTIPLE-possible-outputs function, then source code of this function cannot be copy/pasted into an original engine.

Application:

Process for designing new original chess engine to compete in ICGA:

a) Divide all Crafty functions into the 2 categories, one->one and one->many.

b) Write new chess engine that comprises copy/pasted source code of ALL of Crafty's one->one functions.

c) Write all the other one->many functions utilizing all the state-of-the-art chess engine heuristics ideas.

Voila! Original chess engine?

That is my thinking, yes. It is not an "accepted practice" however. At present, all we have is a very vague concept of clone/derivative. And the most constrained definition is 100% original code. That seems arbitrary and draconian since we can all still use printf(), or built-in PRNGs, etc..

[kingliveson]

one-input -> one-output is pretty clear and well-defined. The minute you reach one-input -> multiple possible outputs, you cross the line. But not before, IMHO. Note that this is a suggestion. NO one has adopted it as a rule or policy...

Is this correct, then?

1) If one-input-one-output function, then source code of this function can be copy/pasted into an original engine.

2) If one-input-MULTIPLE-possible-outputs function, then source code of this function cannot be copy/pasted into an original engine.

Application:

Process for designing new original chess engine to compete in ICGA:

a) Divide all Crafty functions into the 2 categories, one->one and one->many.

b) Write new chess engine that comprises copy/pasted source code of ALL of Crafty's one->one functions.

c) Write all the other one->many functions utilizing all the state-of-the-art chess engine heuristics ideas.

Voila! Original chess engine?

That is my thinking, yes. It is not an "accepted practice" however. At present, all we have is a very vague concept of clone/derivative. And the most constrained definition is 100% original code. That seems arbitrary and draconian since we can all still use printf(), or built-in PRNGs, etc..

As a software designer, you know when you are doing what your are not supposed to do when developing an application.

[hyatt]

You would think. But I am not so sure, based on past experiences.

[Bo Persson]

one-input -> one-output is pretty clear and well-defined. The minute you reach one-input -> multiple possible outputs, you cross the line. But not before, IMHO. Note that this is a suggestion. NO one has adopted it as a rule or policy...

Is this correct, then?

1) If one-input-one-output function, then source code of this function can be copy/pasted into an original engine.

2) If one-input-MULTIPLE-possible-outputs function, then source code of this function cannot be copy/pasted into an original engine.

No.

Source code is text, and is copyrighted just like books and newspaper articles, and web pages. You can't copy that without permission.

However, and I think that's what Bob is hinting at, for a small, well defined function it is very hard to PROVE that you copied it (unless you also copy all the comments verbatim ). To be a bit cynical, what is legal is actually what you get away with. Innocent until proven guilty!

For these small code snippets, we have the additional quirk that a disassembled version of my MemberCount function will look exactly like the "disassembled" version of Crafty's asm code. We can all see that it is not because I copied the code from Crafty, but because I, Bob, and the MS compiler writers have all read about the bit twiddling techniques Gerd linked to. Even the compiler understands the intention, and generates the correct code!

In this case it is hard to accuse anybody of stealing the technique, because "everybody" knows about it already.

So, if you have one small function that is identical, it is legal because of the "get away with it" rule. If your have hundreds of identical functions, you will be in more trouble!

[benstoker]

one-input -> one-output is pretty clear and well-defined. The minute you reach one-input -> multiple possible outputs, you cross the line. But not before, IMHO. Note that this is a suggestion. NO one has adopted it as a rule or policy...

Is this correct, then?

1) If one-input-one-output function, then source code of this function can be copy/pasted into an original engine.

2) If one-input-MULTIPLE-possible-outputs function, then source code of this function cannot be copy/pasted into an original engine.

No.

Source code is text, and is copyrighted just like books and newspaper articles, and web pages. You can't copy that without permission.

However, and I think that's what Bob is hinting at, for a small, well defined function it is very hard to PROVE that you copied it (unless you also copy all the comments verbatim ). To be a bit cynical, what is legal is actually what you get away with. Innocent until proven guilty!

For these small code snippets, we have the additional quirk that a disassembled version of my MemberCount function will look exactly like the "disassembled" version of Crafty's asm code. We can all see that it is not because I copied the code from Crafty, but because I, Bob, and the MS compiler writers have all read about the bit twiddling techniques Gerd linked to. Even the compiler understands the intention, and generates the correct code!

In this case it is hard to accuse anybody of stealing the technique, because "everybody" knows about it already.

So, if you have one small function that is identical, it is legal because of the "get away with it" rule. If your have hundreds of identical functions, you will be in more trouble!

Well, well, well. You have really done it now. Hyatt put his imprimatur on my best attempt to express a keep-it-simple-stupid guideline for writing an "original" engine, and you come in and blow it all up. I give up. I am convinced now that I will never know or understand whatever the heck it takes to write an "original" chess engine. Because as soon as one expert agrees on a set of criteria, another expert is always there to not just disagree, but completely diagree. If there exists this thing called an "original" engine, I will not know it if it stands before me, I will just take it to be a kind of ascription of "beauty", and that therefore "originality" is in the eye of the beholder.

[hyatt]

one-input -> one-output is pretty clear and well-defined. The minute you reach one-input -> multiple possible outputs, you cross the line. But not before, IMHO. Note that this is a suggestion. NO one has adopted it as a rule or policy...

Is this correct, then?

1) If one-input-one-output function, then source code of this function can be copy/pasted into an original engine.

2) If one-input-MULTIPLE-possible-outputs function, then source code of this function cannot be copy/pasted into an original engine.

No.

Source code is text, and is copyrighted just like books and newspaper articles, and web pages. You can't copy that without permission.

However, and I think that's what Bob is hinting at, for a small, well defined function it is very hard to PROVE that you copied it (unless you also copy all the comments verbatim ). To be a bit cynical, what is legal is actually what you get away with. Innocent until proven guilty!

For these small code snippets, we have the additional quirk that a disassembled version of my MemberCount function will look exactly like the "disassembled" version of Crafty's asm code. We can all see that it is not because I copied the code from Crafty, but because I, Bob, and the MS compiler writers have all read about the bit twiddling techniques Gerd linked to. Even the compiler understands the intention, and generates the correct code!

In this case it is hard to accuse anybody of stealing the technique, because "everybody" knows about it already.

So, if you have one small function that is identical, it is legal because of the "get away with it" rule. If your have hundreds of identical functions, you will be in more trouble!

Well, well, well. You have really done it now. Hyatt put his imprimatur on my best attempt to express a keep-it-simple-stupid guideline for writing an "original" engine, and you come in and blow it all up. I give up. I am convinced now that I will never know or understand whatever the heck it takes to write an "original" chess engine. Because as soon as one expert agrees on a set of criteria, another expert is always there to not just disagree, but completely diagree. If there exists this thing called an "original" engine, I will not know it if it stands before me, I will just take it to be a kind of ascription of "beauty", and that therefore "originality" is in the eye of the beholder.

It is messy. But I am still of the "let's make progress". Slate/Atkin (and apparently Donskoy in the Soviet Union) developed the original bitboard approach to chess. With the ugly incremental updating stuff. I improved on that significantly with rotated bitboards. The Pradu found a more flexible (and far simpler) approach based on perfect hashing, which we now call magic move generation.

It is a simple idea, and it makes no sense for everyone to write code to develop the optimal magic numbers, any more than it makes no sense to require everyone to create their own endgame tables and the code to probe them.

So from a "progress" perspective, I can accept some direct copying. All in the framework of "mutual cooperation and sharing." But that only goes so far as the code is a 1:1 mapping of all possible inputs to one possible output for each.

My approach is not copyright-compatible, because legally, nothing can be copied verbatim. I have modified that to be a "rational copyright with respect to computer chess programs" which is a bit less restrictive while still preventing "too much" copying...

Many won't agree, so the debate will take some time. But we have to be careful. I have a copyright bitboard generator, my old rotated stuff. Pradu (buzz) has his magic stuff. A lot of programs will be disallowed if we go too far. Eugene originally developed egtb.cpp as part of Crafty. He might give me permission to be the one legal user, or he might choose someone else (or no one else). You can sort of see where this goes. It would take us back several years if we are too draconian.