Существует несколько возможностей, и одна из которых приводит к минимальному количеству команд или быстрейшему времени выполнения, зависит от используемой архитектуры машины и используемого компилятора.Некоторые архитектуры предлагают ANDN инструкции, другие поддерживают логические инструкции с тремя входами, третьи объединяют сдвиги с логическими операциями.Ниже я показываю три варианта, которые проходят исчерпывающий тест.
Два подхода состоят в том, чтобы либо основывать вывод на проверке равенства байтов с помощью 0xFF, либо на байтовом тесте «больше чем» для 0xFE.Они выбираются через FUNC_VARIANT.Тест «больше чем» является дополнительным основанием для теста «меньше чем», для которого предусмотрены два варианта реализации, выбранные с помощью LTU_VARIANT.
. Отмечены источники алгоритмов для умной побайтной обработки.в комментариях.Вообще говоря, на промежуточных этапах требуется определенное количество маскирования, чтобы предотвратить обработку конкретного байта для воздействия на соседние байты.
Обратите внимание, что код может быть легко адаптирован для обработки по восемь байтов за раз, скореечем четыре, как указано в вопросе.
Быстрая проверка с Проводник компилятора показывает, что с gcc, FUNC_VARIANT=1, LTU_VARIANT=0 компилируется в кратчайшие последовательности команд для обоих x86-64 и ARM64 .Это, возможно, не обязательно приведет к максимально возможной производительности.
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#define FUNC_VARIANT 0
#define LTU_VARIANT 0
#define UINT32_H4 0x80808080U // byte-wise sign bits (MSBs)
#define UINT32_L4 0x01010101U // byte-wise LSBs
#define UINT32_M4 0xffffffffU // byte-wise maximum
uint32_t sign_to_bool4 (uint32_t a)
{
return (a >> 7) & UINT32_L4;
}
uint32_t vhaddu4 (uint32_t a, uint32_t b)
{
/* Peter L. Montgomery's observation (newsgroup comp.arch, 2000/02/11,
https://groups.google.com/d/msg/comp.arch/gXFuGZtZKag/_5yrz2zDbe4J):
(A+B)/2 = (A AND B) + (A XOR B)/2.
*/
return (a & b) + (((a ^ b) >> 1) & ~UINT32_H4);
}
uint32_t ltu4_core (uint32_t a, uint32_t b)
{
/* Sebastiano Vigna, "Broadword implementation of rank/select queries."
In: International Workshop on Experimental and Efficient Algorithms,
pp. 154-168, Springer Berlin Heidelberg, 2008.
*/
return (((a | UINT32_H4) - (b & ~UINT32_H4)) | (a ^ b)) ^ (a | ~b);
}
uint32_t vsetltu4 (uint32_t a, uint32_t b)
{
#if LTU_VARIANT==1
return sign_to_bool4 (ltu4_core (a, b));
#else // LTU_VARIANT
return sign_to_bool4 (vhaddu4 (~a, b));
#endif // LTU_VARIANT
}
uint32_t vsetgtu4 (uint32_t a, uint32_t b)
{
return vsetltu4 (b, a);
}
uint32_t vseteq4 (uint32_t a, uint32_t b)
{
uint32_t r, t;
/* Alan Mycroft's null-byte detection algorithm (newsgroup comp.lang.c, 1987/04/08,
https://groups.google.com/forum/#!original/comp.lang.c/2HtQXvg7iKc/xOJeipH6KLMJ):
null_byte(x) = ((x - 0x01010101) & (~x & 0x80808080))
*/
r = a ^ b; // 0x00 if a == b
t = r | UINT32_H4; // set msbs, to catch carry out
r = r ^ t; // extract msbs, msb = 1 if r < 0x80
t = t - UINT32_L4; // sign bit = 0, if r was 0x00 or 0x80
t = r & ~t; // sign_bit = 1, if r was 0x00
r = t >> 7; // convert to bool
return r;
}
uint32_t func (uint32_t a)
{
#if FUNC_VARIANT == 1
return vsetgtu4 (a, ~UINT32_L4); // byte-wise a >ᶸ 0xFE
#else // FUNC_VARIANT
return vseteq4 (a, UINT32_M4); // byte-wise a == 0xFF
#endif // FUNC_VARIANT
}
uint32_t ref_func (uint32_t a)
{
uint8_t a0 = (uint8_t)((a >> 0) & 0xff);
uint8_t a1 = (uint8_t)((a >> 8) & 0xff);
uint8_t a2 = (uint8_t)((a >> 16) & 0xff);
uint8_t a3 = (uint8_t)((a >> 24) & 0xff);
int p0 = (a0 == 0xff);
int p1 = (a1 == 0xff);
int p2 = (a2 == 0xff);
int p3 = (a3 == 0xff);
return (((uint32_t)p3 << 24) | ((uint32_t)p2 << 16) |
((uint32_t)p1 << 8) | ((uint32_t)p0 << 0));
}
int main (void)
{
uint32_t res, ref, x = 0;
do {
res = func (x);
ref = ref_func (x);
if (res != ref) {
printf ("error @ %08x: res=%08x ref=%08x\n", x, res, ref);
return EXIT_FAILURE;
}
x++;
} while (x);
printf ("test passed\n");
return EXIT_SUCCESS;
}