| 1 | #! /bin/false | ||
| 2 | |||
| 3 | # Copyright (C) 2021-2026 Guido Flohr <guido.flohr@cantanea.com>, | ||
| 4 | # all rights reserved. | ||
| 5 | |||
| 6 | # This program is free software. It comes without any warranty, to | ||
| 7 | # the extent permitted by applicable law. You can redistribute it | ||
| 8 | # and/or modify it under the terms of the Do What the Fuck You Want | ||
| 9 | # to Public License, Version 2, as published by Sam Hocevar. See | ||
| 10 | # http://www.wtfpl.net/ for more details. | ||
| 11 | |||
| 12 | # This is a macro that is not intended to run standalone. | ||
| 13 | |||
| 14 | ## no critic (TestingAndDebugging::RequireUseStrict) | ||
| 15 | |||
| 16 | # This is a variation of the well-known algorithm. The if branch is | ||
| 17 | # necessary because under the integer pragma, all operands and results of | ||
| 18 | # the bitwise operators are treated as signed. | ||
| 19 | # | ||
| 20 | # At first glance, it looks like this will slow down things. But with evenly | ||
| 21 | # distributed input, the opposite is true. For about half of the possible | ||
| 22 | # input values, it is a lot faster, for the other half it is a little slower | ||
| 23 | # All in all, it is faster but ... | ||
| 24 | # | ||
| 25 | # Alas, our input is not evenly distributed because we are working on bitboards | ||
| 26 | # representing the position of chess pieces. The most densely populated | ||
| 27 | # bitboard that I can think of is the bitboard of all pieces. It has 32 of | ||
| 28 | # 64 bits set. The odds that the left-most bit is set are therefore | ||
| 29 | # 0.5 The less pieces a bitboard represents (pawns, knights, bishops, ... | ||
| 30 | # kings), the less likely it is that the left-most bit is set, and then the | ||
| 31 | # extra branch becomes less and less useful, thus more and more expensive. | ||
| 32 | # | ||
| 33 | # In other words, yes, it is less efficient than the unodified algorithm. | ||
| 34 | (do { | ||
| 35 | my $B = $bb; | ||
| 36 | if ($B & 0x8000_0000_0000_0000) { | ||
| 37 | 0x8000_0000_0000_0000; | ||
| 38 | } else { | ||
| 39 | $B |= $B >> 1; | ||
| 40 | $B |= $B >> 2; | ||
| 41 | $B |= $B >> 4; | ||
| 42 | $B |= $B >> 8; | ||
| 43 | $B |= $B >> 16; | ||
| 44 | $B |= $B >> 32; | ||
| 45 | $B - ($B >> 1); | ||
| 46 | } | ||
| 47 | }) |