SoE segmented

//    https://codereview.stackexchange.com/q/189083

//    https://pastebin.com/0F6fiEAD

/*                    old-ns-new               old-s-new
      primes <   25     47    47    p < 2^31   7.0   2.0
                 50     62    63        2^32  15.0   4.2
                100     78    78
                200    141   110         1e9         0.9
                400    218   187         2e9         1.8
                800    406   344         4e9         3.9
               1600    718   639
               3200   1435  1295
               6400   2855  2590                            */

//    https://pastebin.com/xK6c0EVc
//    ~ 10 % faster (not for small limits ;)

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <ctime>
#include <Windows.h>
using namespace std;
typedef unsigned int u32;
vector<u32> x; vector<u32> p;

void buildX(u32 m)  // mark odd composites
{
    m -= m / ~0u; m += m & 1; m >>= 1;
    u32 r0, r1 = 0, a = 1, b = 1, c = 1, d = m >> 5;
    x.resize(d + 1); x[0] = 0x9b4b3491;
    for (;;)                                      // 3x23 3x25 3x27 ...
    {
        if (a > d) break; x[a++] = 0x24924924;
        if (a > d) break; x[a++] = 0x49249249;
        if (a > d) break; x[a++] = 0x92492492;
    }
    for (;;)                                      // 5x13 5x15 5x17 ...
    {
        if (b > d) break; x[b++] |= 0x42108421;
        if (b > d) break; x[b++] |= 0x10842108;
        if (b > d) break; x[b++] |= 0x84210842;
        if (b > d) break; x[b++] |= 0x21084210;
        if (b > d) break; x[b++] |= 0x08421084;
    }
    for (;;)                                      // 7x11 7x13 7x15 ...
    {
        if (c > d) break; x[c++] |= 0x08102040;
        if (c > d) break; x[c++] |= 0x40810204;
        if (c > d) break; x[c++] |= 0x04081020;
        if (c > d) break; x[c++] |= 0x20408102;
        if (c > d) break; x[c++] |= 0x02040810;
        if (c > d) break; x[c++] |= 0x10204081;
        if (c > d) break; x[c++] |= 0x81020408;
    }
    while ((r0 = r1) < m)  // L1 cache 64 KB / 2 = 0x40000
    {
        if ((r1 += 0x40000) > m) r1 = m;
        for (a = 11, b = 60, c = 20; b < r1; a += 2, b += c += 4)
            if ((x[a >> 6] & 1 << (a >> 1)) == 0)
            {
                if ((d = b) < r0)
                {
                    d += (r0 - d) / a * a;
                    if (d < r0) d += a;
                }
                while (d < r1) { x[d >> 5] |= 1 << d; d += a; }
            }
    }
    x[m >> 5] |= ~0u << m;
}

void countPrimes()
{
    u32 c = 1; int i = x.size() - 1;
    while (i >= 0) c += __popcnt(~x[i--]);
    p.resize(c);
}

void primes(u32 m)  // primes <= m
{
    if (m > 1)
    {
        buildX(m); countPrimes(); p[0] = 2;
        u32 u = ~0u, v = ~0u, xi; DWORD tz;
        for (int i = 0, n = 1, c = p.size(); n < c; v = u += 64)
            for (xi = ~x[i++]; xi; p[n++] = v += (tz + 1) << 1)
            {
                _BitScanForward(&tz, xi); xi >>= tz; xi >>= 1;
            }
    }
}

int main()
{
    primes(1000);
    for (u32 m = 25; m < 6401; m <<= 1)  // for (u32 m = 0; m < 9; m++)
    {
        primes(m);
        if (m > 1)
        {
            u32 maxP = p[p.size() - 1];
            cout << "largest prime <= " << m << ": " << maxP << "  ";
        }
        clock_t clock0 = clock();
        for (int i = 1000000; i; i--)
        {
            x.resize(0); p.resize(0); primes(m);
        }
        cout << clock() - clock0 << " ns: ";
        cout << p.size() << " primes" << endl << endl;
    }
    x.resize(0); p.resize(0); u32 m = (u32)~0u >> 0;
    clock_t clock0 = clock(); primes(m);
    cout << clock() - clock0 << " ms: ";
    cout << p.size() << " primes <= " << m;
    for (int j = p.size(), i = j - 5; i < j;) cout << endl << p[i++];
    getchar();
}


//  void buildX(u32 m) {
//      m -= m / ~0u; m += m & 1; m >>= 1;
//      u32 r0, r1 = 0, a = 1, b = 1, c = 1, d = m >> 5;
//      x.resize(d + 1); x[0] = 0x9b4b3491;
//  L0: if (a > d) goto L1; x[a++] = 0x24924924;;
//      if (a > d) goto L1; x[a++] = 0x49249249;;
//      if (a > d) goto L1; x[a++] = 0x92492492;; goto L0;
//  L1: if (b > d) goto L2; x[b++] |= 0x42108421;
//      if (b > d) goto L2; x[b++] |= 0x10842108;
//      if (b > d) goto L2; x[b++] |= 0x84210842;
//      if (b > d) goto L2; x[b++] |= 0x21084210;
//      if (b > d) goto L2; x[b++] |= 0x08421084; goto L1;
//  L2: if (c > d) goto L3; x[c++] |= 0x08102040;
//      if (c > d) goto L3; x[c++] |= 0x40810204;
//      if (c > d) goto L3; x[c++] |= 0x04081020;
//      if (c > d) goto L3; x[c++] |= 0x20408102;
//      if (c > d) goto L3; x[c++] |= 0x02040810;
//      if (c > d) goto L3; x[c++] |= 0x10204081;
//      if (c > d) goto L3; x[c++] |= 0x81020408; goto L2;
//  L3: if ((r0 = r1) == m) { x[m >> 5] |= ~0u << m; return; }
//      if ((r1 += 0x40000) > m) r1 = m;
//      for (a = 9, b = 60, c = 20; b < r1; b += c += 4)
//          if ((x[(a += 2) >> 6] & 1 << (a >> 1)) == 0) {
//              if ((d = b) < r0) d += (r0 - d + a ^ 1) / a * a;
//              while (d < r1) { x[d >> 5] |= 1 << d; d += a; }
//          } goto L3;
//  }

//  void countPrimes() {
//      u32 c = 1, xi;
//      for (int i = x.size() - 1; i >= 0; i--)
//          for (xi = ~x[i]; xi; xi &= xi - 1) c++;
//      p.resize(c);
//  }