Как можно сделать этот динамический код битового диапазона GCC-совместимым для 64-битных компиляторов?

Question

Я пытаюсь обновить для Linux, GCC и 64-битного использования и сохранить в github Программное обеспечение Кена Сильвермана Paint N Draw 3D C.Я получил его разрешение, но он слишком занят, чтобы помочь.Я не хочу делать плохую работу, и я не мелкий эксперт, поэтому я хотел бы исправить основные части, прежде чем загружать его.

В своем коде pnd3d.c он использовал структуруназывается bitmal_t *, который содержит malloc (я думаю, что его элемент mal означает размер malloc) и размер, чтобы указать воксельное расстояние в виде цепочки битов без знака int (в 2009 году это была 32-битная) среди битовкаскадный набор 32-битных целыхТаким образом, в основном расстояние является функцией количества битов в (1) вдоль расширенной цепочки битов.Для столкновений он смотрит вверх и вниз на нули и единицы.

Вот его bitmal_t:

    //buf: cast to: octv_t* or surf_t*
    //bit: 1 bit per sizeof(buf[0]); 0=free, 1=occupied
typedef struct bit { void *buf; unsigned int mal, *bit, ind, num, siz; } bitmal_t;

Вот его код поиска диапазона, который идет вверх и вниз по диапазону битов, ищаодин или ноль.Я разместил его оригиналы, а не мою дрянную нерабочую версию.

Вот все фрагменты кода, которые вам понадобятся для его воспроизведения.

static __forceinline int dntil0 (unsigned int *lptr, int z, int zsiz)
{
    //   //This line does the same thing (but slow & brute force)
    //while ((z < zsiz) && (lptr[z>>5]&(1<<KMOD32(z)))) z++; return(z);
    int i;
        //WARNING: zsiz must be multiple of 32!
    i = (lptr[z>>5]|((1<<KMOD32(z))-1)); z &= ~31;
    while (i == 0xffffffff)
    {
        z += 32; if (z >= zsiz) return(zsiz);
        i = lptr[z>>5];
    }
    return(bsf(~i)+z);
}

static __forceinline int uptil0 (unsigned int *lptr, int z)
{
    //   //This line does the same thing (but slow & brute force)
    //while ((z > 0) && (lptr[(z-1)>>5]&(1<<KMOD32(z-1)))) z--; return(z);
    int i;
    if (!z) return(0); //Prevent possible crash
    i = (lptr[(z-1)>>5]|(-1<<KMOD32(z))); z &= ~31;
    while (i == 0xffffffff)
    {
        z -= 32; if (z < 0) return(0);
        i = lptr[z>>5];
    }
    return(bsr(~i)+z+1);
}

static __forceinline int dntil1 (unsigned int *lptr, int z, int zsiz)
{
    //   //This line does the same thing (but slow & brute force)
    //while ((z < zsiz) && (!(lptr[z>>5]&(1<<KMOD32(z))))) z++; return(z);
    int i;
        //WARNING: zsiz must be multiple of 32!
    i = (lptr[z>>5]&(-1<<KMOD32(z))); z &= ~31;
    while (!i)
    {
        z += 32; if (z >= zsiz) return(zsiz);
        i = lptr[z>>5];
    }
    return(bsf(i)+z);
}

static __forceinline int uptil1 (unsigned int *lptr, int z)
{
    //   //This line does the same thing (but slow & brute force)
    //while ((z > 0) && (!(lptr[(z-1)>>5]&(1<<KMOD32(z-1))))) z--; return(z);
    int i;
    if (!z) return(0); //Prevent possible crash
    i = (lptr[(z-1)>>5]&((1<<KMOD32(z))-1)); z &= ~31;
    while (!i)
    {
        z -= 32; if (z < 0) return(0);
        i = lptr[z>>5];
    }
    return(bsr(i)+z+1);
}

Вот его диапазон установки функций единиц и нулей:

//Set all bits in vbit from (x,y,z0) to (x,y,z1-1) to 0's
#ifndef _WIN64

static __forceinline void setzrange0 (void *vptr, int z0, int z1)
{
    int z, ze, *iptr = (int *)vptr;
    if (!((z0^z1)&~31)) { iptr[z0>>5] &= ((~(-1<<z0))|(-1<<z1)); return; }
    z = (z0>>5); ze = (z1>>5);
    iptr[z] &=~(-1<<z0); for(z++;z<ze;z++) iptr[z] = 0;
    iptr[z] &= (-1<<z1);
}

    //Set all bits in vbit from (x,y,z0) to (x,y,z1-1) to 1's
static __forceinline void setzrange1 (void *vptr, int z0, int z1)
{
    int z, ze, *iptr = (int *)vptr;
    if (!((z0^z1)&~31)) { iptr[z0>>5] |= ((~(-1<<z1))&(-1<<z0)); return; }
    z = (z0>>5); ze = (z1>>5);
    iptr[z] |= (-1<<z0); for(z++;z<ze;z++) iptr[z] = -1;
    iptr[z] |=~(-1<<z1);
}

#else

static __forceinline void setzrange0 (void *vptr, __int64 z0, __int64 z1)
{
    unsigned __int64 z, ze, *iptr = (unsigned __int64 *)vptr;
    if (!((z0^z1)&~63)) { iptr[z0>>6] &= ((~(LL(-1)<<z0))|(LL(-1)<<z1)); return; }
    z = (z0>>6); ze = (z1>>6);
    iptr[z] &=~(LL(-1)<<z0); for(z++;z<ze;z++) iptr[z] = LL(0);
    iptr[z] &= (LL(-1)<<z1);
}

    //Set all bits in vbit from (x,y,z0) to (x,y,z1-1) to 1's
static __forceinline void setzrange1 (void *vptr, __int64 z0, __int64 z1)
{
    unsigned __int64 z, ze, *iptr = (unsigned __int64 *)vptr;
    if (!((z0^z1)&~63)) { iptr[z0>>6] |= ((~(LL(-1)<<z1))&(LL(-1)<<z0)); return; }
    z = (z0>>6); ze = (z1>>6);
    iptr[z] |= (LL(-1)<<z0); for(z++;z<ze;z++) iptr[z] = LL(-1);
    iptr[z] |=~(LL(-1)<<z1);
}

#endif

Answer 1

Напишите несколько юнит-тестов, которые проходят по оригиналу!

Прежде всего, SSE2 является базовой для x86-64, поэтому вам определенно следует использовать это вместо 64-битных целых чисел.

GCC (в отличие от MSVC) не предполагает нарушений строгого псевдонима, поэтому может потребоваться установить функции диапазона битов (которые приводят входящий указатель к знаку int* (!!) или uint64_t* в зависимости от WIN64 или нет) скомпилировано с -fno-strict-aliasing для точного определения приведения указателя.

Вы можете заменить часть цикла функций set / clear для диапазона битов на memset (который может встроить gcc) или рукописный встроенный цикл SSE, если вы ожидаете, что размер обычно будет маленьким (например, менее 200 байт или поэтому не стоит тратить время на вызов libc memset)

---

Я думаю, что эти dntil0 функции в первом блоке являются просто циклами поиска битов для первого 0 или первого 1 бита, вперед или назад.

Перепишите их с нуля с помощью встроенных функций SSE2 : _mm_cmpeq_epi8 / _mm_movemask_epi8, чтобы найти первый байт, который не равен 0 или 0, а затем используйте bsf или bsr об этом.

См. Исходный код glibc для SSE2 memchr или любую более простую реализацию, оптимизированную для SSE2, чтобы узнать, как выполнить поиск по байту. Или glibc memmem для примера сравнения для , равного , но это легко: вместо поиска ненулевого _mm_movemask_epi8() (указывающего на совпадение), ищите результат, который != 0xffff (все), чтобы указать, что было несоответствие. Используйте bsf или bsr для этой битовой маски, чтобы найти индекс байта в векторе SIMD.

Таким образом, в общей сложности вы будете использовать BSR или BSF дважды в каждой функции: по одному, чтобы найти индекс байта в векторе SIMD, и снова, чтобы найти битовый индекс в целевом байте.

Для функции битового сканирования используйте GCC __builtin_clz или __builtin_ctz, чтобы найти первый 1 бит. Бит тиддлинг: какой бит установлен?

Для поиска первого нуля вместо первого, побитового инвертирования, например __builtin_ctz( ~p[idx] ), где p - это unsigned char* в вашем буфере поиска (который вы использовали _mm_loadu_si128() on), и idx это смещение в этом 16-байтовом окне. (То, что вы вычислили с __builtin_ctz() для результата movemask, который вышел из векторного цикла.)

---

Как работал оригинал:

z -= 32 зацикливается на 32 бита (размер int, потому что это было написано при условии, что оно будет скомпилировано для Windows x86 или x86-64 Windows).

lptr[z>>5]; преобразует битовый индекс в индекс int. Так что это просто цикл по буферу 1 int за один раз.

Когда он находит 4-байтовый элемент != 0xFFFFFFFF, он находит int, содержащий бит, который не равен 1; то есть он содержит бит, который мы ищем. Таким образом, он использует bsf или bsr для битового сканирования и поиска положения этого бита в this int.
Это добавляет это к z (битовая позиция начала этого int).

Это точно такой же алгоритм, который я описал выше, но реализовал одно целое число за раз вместо 16 байтов за раз.

Он действительно должен использовать uint32_t или unsigned int для битовых манипуляций, без подписи int, но он, очевидно, работает правильно на MSVC.

if (z >= zsiz) return(zsiz); Это проверка размера, чтобы выйти из цикла, если бит не найден.