asignación eficiente para un entero finito particular, establece

Question

Busco un pequeño, rápido (en ambas direcciones) biyectiva entre la siguiente lista de números enteros y un subconjunto del rango 0-127:

0x200C, 0x200D, 0x200E, 0x200F, 
0x2013, 0x2014, 0x2015, 0x2017, 
0x2018, 0x2019, 0x201A, 0x201C, 
0x201D, 0x201E, 0x2020, 0x2021, 
0x2022, 0x2026, 0x2030, 0x2039, 
0x203A, 0x20AA, 0x20AB, 0x20AC, 
0x20AF, 0x2116, 0x2122 

Una solución obvia es:

y = x>>2 & 0x40 | x & 0x3f; 
x = 0x2000 | y<<2 & 0x100 | y & 0x3f; 

Editar: me estaba perdiendo algunos de los valores, en particular 0x20Ax, que no funcionan con lo anterior.

Otra solución obvia es una tabla de búsqueda, pero sin hacerla innecesariamente grande, una tabla de búsqueda requeriría alguna reorganización de bit de todos modos y sospecho que la tarea completa se puede lograr mejor con una reorganización de bit simple.

Para los curiosos, esos números mágicos son los únicos puntos de código Unicode "grandes" que aparecen en las páginas de códigos heredadas ISO-8859 y Windows.

Answer 1

sé que es feo, pero a excepción de último valor de todos los otros son ya única si se tiene en cuenta más bajas 6 bits, lo que sólo puede construir y mapa inversa:

int ints[] = {0x200C, 0x200D, 0x200E, 0x200F, 
       0x2013, 0x2014, 0x2015, 0x2017, 
       0x2018, 0x2019, 0x201A, 0x201C, 
       0x201D, 0x201E, 0x2020, 0x2021, 
       0x2022, 0x2026, 0x2030, 0x2039, 
       0x203A, 0x20AA, 0x20AB, 0x20AC, 
       0x20AF, 0x2116, 0x2122}; 

int invmap[64]; 

void mkinvmap() 
{ 
    for (int i=0; i<26; i++) 
     invmap[ints[i]&63] = ints[i]; 
    invmap[0] = 0x2122; 
} 

Después de este mapa inversa cálculo de los dos transformar funciones son

int direct(int x) { return x==0x2122 ? 0 : (x & 63); } 
int inverse(int x) { return invmap[x]; } 

la función direct(x) devolverá un número entre 0 y 63, y la función inverse(x) dado un número entre 0 y 63 devolverá un número entero. Para todos los 27 valores en su lista inverse(direct(x)) == x.

Answer 2

Me gustaría obtener una función de hash simple (y barata) f que elija de una familia f0, f1, ... de funciones que se correspondan con los valores 0..255, digamos. Si tu función de hash fuera aleatoria, según la paradoja de cumpleaños, tendrías algunas colisiones por los valores que te interesan, pero no muchos.

Ahora una secuencia de comandos simple perl (de lo que sea) le permitirá preprocesar sus datos de valor fijo para reducir (o incluso eliminar) las colisiones eligiendo una función apropiada de su conjunto.

Este enfoque tiene la ventaja de que puede renovar la ejecución de preprocesamiento si descubre que olvidó un valor (como ya lo hizo) o algún país extraño decide mapear caracteres Unicode extraños como € en un juego de caracteres de 8 bits.

Y, por cierto, creo que la cantidad de caracteres especiales que están en algunos de los iso-8859-? los conjuntos deben ser mucho más grandes que lo que tienes, aquí, ¿no? Yo los tomaría a todos.

Editar: Después de hacer algunos experimentos un pequeño script Perl me dice que todos los puntos de código Unicode 577 que aparecen en una de las codificaciones ISO-8859 se asignan a diferentes posiciones cuando se reduce módulo 10007 o 10009.

Editar: la tabla siguiente se hace el truco, para el conjunto limitado:

wchar_t const uniqTable[91] = { 
[0x7] = L'\u2116' /* № */, 
[0xD] = L'\uFFFD' /* � */, 
[0xE] = L'\u200C' /* ‌ */, 
[0xF] = L'\u200D' /* ‍ */, 
[0x10] = L'\u200E' /* ‎ */, 
[0x11] = L'\u200F' /* ‏ */, 
[0x13] = L'\u2122' /* ™ */, 
[0x15] = L'\u2013' /* – */, 
[0x16] = L'\u2014' /* — */, 
[0x17] = L'\u2015' /* ― */, 
[0x19] = L'\u2017' /* ‗ */, 
[0x1A] = L'\u2018' /* ‘ */, 
[0x1B] = L'\u2019' /* ’ */, 
[0x1C] = L'\u201A' /* ‚ */, 
[0x1E] = L'\u201C' /* “ */, 
[0x1F] = L'\u201D' /* ” */, 
[0x20] = L'\u201E' /* „ */, 
[0x22] = L'\u2020' /* † */, 
[0x23] = L'\u2021' /* ‡ */, 
[0x24] = L'\u2022' /* • */, 
[0x28] = L'\u2026' /* … */, 
[0x32] = L'\u2030' /* ‰ */, 
[0x3B] = L'\u2039' /* ‹ */, 
[0x3C] = L'\u203A' /* › */, 
[0x51] = L'\u20AA' /* ₪ */, 
[0x52] = L'\u20AB' /* ₫ */, 
[0x53] = L'\u20AC' /* € */, 
[0x56] = L'\u20AF' /* ₯ */, 
}; 

Answer 3

Por ensayo & de error, que llegó a la siguiente algoritmo:

#include <assert.h> 
#include <stdio.h> 

static const unsigned CODES[] = { 
    0x200C, 0x200D, 0x200E, 0x200F, 
    0x2013, 0x2014, 0x2015, 0x2017, 
    0x2018, 0x2019, 0x201A, 0x201C, 
    0x201D, 0x201E, 0x2020, 0x2021, 
    0x2022, 0x2026, 0x2030, 0x2039, 
    0x203A, 0x20AA, 0x20AB, 0x20AC, 
    0x20AF, 0x2116, 0x2122 
}; 

static unsigned enc(unsigned value) 
{ 
    return (value & 0x3F) + (value & 0x180)/4; 
} 

static unsigned dec(unsigned value) 
{ 
    return 0x2000 + value + ((value & 0x40) >> 6) * 3 * 
     (0x20 + (value & 0x10) * 2 + (value & 0x20)); 
} 

int main(void) 
{ 
    const unsigned *const END = CODES + sizeof CODES/sizeof *CODES; 
    const unsigned *current = CODES; 
    for(; current < END; ++current) 
    { 
     printf("%04x -> %02x -> %04x\n", 
      *current, enc(*current), dec(enc(*current))); 

     assert(enc(*current) < 0x80); 
     assert(dec(enc(*current)) == *current); 
    } 

    return 0; 
} 

A veces, ritmos de evolución diseño inteligente incluso cuando se escribe código;)

Answer 4

Este método usa la multiplicación en un campo finito LD:

#define PRIME 0x119 
#define OFFSET1 0x00f 
#define OFFSET2 0x200c 
#define OFFSET3 (OFFSET2 - OFFSET1) 
#define MULTIPLIER 2 
#define INVERSE 0x8d 

unsigned map(unsigned n) 
{ 
    return ((n - OFFSET3) * MULTIPLIER) % PRIME; 
} 

unsigned unmap(unsigned m) 
{ 
    return ((m * INVERSE) + PRIME - OFFSET1) % PRIME + OFFSET2; 
} 

map() convierte los puntos de Unicode a los números únicos de 7 bits, y unmap() hace lo contrario. Tenga en cuenta que gcc al menos es capaz de compilar esto en código x86 que no utiliza ninguna operación de división, ya que el módulo es una constante.