cpp/openttd-patchpack/source Changeset - r28517:a50813eb32a8

Changeset - r28517:a50813eb32a8

Parent rev.

Child rev.

[Not reviewed]

master

0 4 0

Rubidium - 11 months ago 2024-01-18 17:40:52
rubidium@openttd.org

Codechange: replace hand written function to find first/last bit with C++ variant

4 files changed with 31 insertions and 60 deletions:

src/core/bitmath_func.cpp

src/core/bitmath_func.hpp

src/graph_gui.cpp

src/signal.cpp

0 comments (0 inline, 0 general)

src/core/bitmath_func.cpp

➞

Show inline comments

@@ @@ -19,62 +19,6 @@ const uint8_t _ffb_64[64] = { @@
 ,  0,  1,  0,  2,  0,  1,  0,
 ,  0,  1,  0,  2,  0,  1,  0,
 ,  0,  1,  0,  2,  0,  1,  0,
 ,  0,  1,  0,  2,  0,  1,  0,
 ,  0,  1,  0,  2,  0,  1,  0,
 };
 /**
  * Search the first set bit in a 64 bit variable.
+ *
  * This algorithm is a static implementation of a log
  * congruence search algorithm. It checks the first half
  * if there is a bit set search there further. And this
  * way further. If no bit is set return 0.
+ *
  * @param x The value to search
  * @return The position of the first bit set
  */
 uint8_t FindFirstBit(uint64_t x)
+{
 	if (x == 0) return 0;
 	/* The macro FIND_FIRST_BIT is better to use when your x is
 	  not more than 128. */
 	uint8_t pos = 0;
 	if ((x & 0xffffffffULL) == 0) { x >>= 32; pos += 32; }
 	if ((x & 0x0000ffffULL) == 0) { x >>= 16; pos += 16; }
 	if ((x & 0x000000ffULL) == 0) { x >>= 8;  pos += 8;  }
 	if ((x & 0x0000000fULL) == 0) { x >>= 4;  pos += 4;  }
 	if ((x & 0x00000003ULL) == 0) { x >>= 2;  pos += 2;  }
 	if ((x & 0x00000001ULL) == 0) { pos += 1; }
 	return pos;
+}
 /**
  * Search the last set bit in a 64 bit variable.
+ *
  * This algorithm is a static implementation of a log
  * congruence search algorithm. It checks the second half
  * if there is a bit set search there further. And this
  * way further. If no bit is set return 0.
+ *
  * @param x The value to search
  * @return The position of the last bit set
  */
 uint8_t FindLastBit(uint64_t x)
+{
 	if (x == 0) return 0;
 	uint8_t pos = 0;
 	if ((x & 0xffffffff00000000ULL) != 0) { x >>= 32; pos += 32; }
 	if ((x & 0x00000000ffff0000ULL) != 0) { x >>= 16; pos += 16; }
 	if ((x & 0x000000000000ff00ULL) != 0) { x >>= 8;  pos += 8;  }
 	if ((x & 0x00000000000000f0ULL) != 0) { x >>= 4;  pos += 4;  }
 	if ((x & 0x000000000000000cULL) != 0) { x >>= 2;  pos += 2;  }
 	if ((x & 0x0000000000000002ULL) != 0) { pos += 1; }
 	return pos;
+}

src/core/bitmath_func.hpp

➞

Show inline comments

@@ @@ -219,14 +219,41 @@ inline uint8_t FindFirstBit2x64(const in @@
 		return FIND_FIRST_BIT((value >> 8) & 0x3F) + 8;
 	} else {
 		return FIND_FIRST_BIT(value & 0x3F);
+	}
+}
 uint8_t FindFirstBit(uint64_t x);
 uint8_t FindLastBit(uint64_t x);
 /**
  * Search the first set bit in a value.
  * When no bit is set, it returns 0.
+ *
  * @param x The value to search.
  * @return The position of the first bit set.
  */
 template <typename T>
 constexpr uint8_t FindFirstBit(T x)
+{
 	if (x == 0) return 0;
 	return std::countr_zero(x);
+}
 /**
  * Search the last set bit in a value.
  * When no bit is set, it returns 0.
+ *
  * @param x The value to search.
  * @return The position of the last bit set.
  */
 template <typename T>
 constexpr uint8_t FindLastBit(T x)
+{
 	if (x == 0) return 0;
 	return std::numeric_limits<T>::digits - std::countl_zero(x) - 1;
+}
 /**
  * Clear the first bit in an integer.
+ *
  * This function returns a value where the first bit (from LSB)
  * is cleared.

src/graph_gui.cpp

➞

Show inline comments

@@ @@ -437,13 +437,13 @@ protected: @@
 						 * significant bits can just be removed.
+						 *
 						 * If there are more bits needed than would fit in a 32 bits
 						 * integer, so at about 31 bits because of the sign bit, the
 						 * least significant bits are removed.
 						 */
 						int mult_range = FindLastBit(x_axis_offset) + FindLastBit(abs(datapoint));
+						int mult_range = FindLastBit<uint32_t>(x_axis_offset) + FindLastBit<uint64_t>(abs(datapoint));
 						int reduce_range = std::max(mult_range - 31, 0);
 						/* Handle negative values differently (don't shift sign) */
 						if (datapoint < 0) {
 							datapoint = -(abs(datapoint) >> reduce_range);
 						} else {

src/signal.cpp

➞

Show inline comments

@@ @@ -306,13 +306,13 @@ static SigFlags ExploreSegment(Owner own @@
+				}
 				if (HasSignals(tile)) { // there is exactly one track - not zero, because there is exit from this tile
 					Track track = TrackBitsToTrack(tracks_masked); // mask TRACK_BIT_X and Y too
 					if (HasSignalOnTrack(tile, track)) { // now check whole track, not trackdir
 						SignalType sig = GetSignalType(tile, track);
-						Trackdir trackdir = (Trackdir)FindFirstBit((tracks * 0x101) & _enterdir_to_trackdirbits[enterdir]);
+						Trackdir trackdir = (Trackdir)FindFirstBit((tracks * 0x101U) & _enterdir_to_trackdirbits[enterdir]);
 						Trackdir reversedir = ReverseTrackdir(trackdir);
 						/* add (tile, reversetrackdir) to 'to-be-updated' set when there is
 						 * ANY conventional signal in REVERSE direction
 						 * (if it is a presignal EXIT and it changes, it will be added to 'to-be-done' set later) */
 						if (HasSignalOnTrackdir(tile, reversedir)) {
 							if (IsPbsSignal(sig)) {

0 comments (0 inline, 0 general)