La codificación Manchester es un protocolo de telecomunicaciones utilizado en las comunicaciones de radio que garantiza las transiciones de bits a intervalos regulares para que un receptor pueda recuperar la frecuencia de reloj de los datos en sí. Duplica la tasa de bits, pero es barata y fácil de implementar. Es ampliamente utilizado por los operadores de radioaficionados.

El concepto es muy simple: a nivel de hardware, el reloj y las líneas de datos simplemente se combinan en XOR. En el software, esto se representa como la conversión de un flujo de bits de entrada en un flujo de salida de doble velocidad, con cada entrada '1' traducida a '01' y cada entrada '0' traducida a '10'.

Este es un problema fácil, pero está abierto a muchas implementaciones debido a su naturaleza de flujo de bits. Es decir, la codificación es conceptualmente un proceso bit a bit en lugar de un proceso byte a byte. Entonces, todos estamos de acuerdo en la endianidad, los bits menos significativos de la entrada se convierten en el byte menos significativo de la salida.

¡Tiempo de golf! Escriba una función que, dada una matriz arbitraria de bytes de longitud, devuelva una matriz de esos datos codificados por Manchester.

La entrada y la salida deben considerarse little-endian, el byte menos significativo primero y el BIT menos significativo primero en el flujo de bits.

Dibujo de flujo de bits ASCII :

bit #      5 4 3 2 1 0                                5  4  3  2  1  0
IN ------- 1 0 1 0 1 1 ---> [manchester encoder] ---  01 10 01 10 01 01 ----> OUT

Ejemplos :

Example 1 (hex):
       LSB              MSB     <-- least sig BYTE first
IN : [0x10, 0x02]  
OUT: [0xAA, 0xA9, 0xA6, 0xAA]  

Example 1 (binary):
      msb  lsb                      msb  lsb  <-- translated hex, so msb first
BIN: [00010000, 00000010]                     <-- least sig NIBBLE...
BIN: [10101010, 10101001, 10100110, 10101010] <-- becomes least sig BYTE
         LSB                           MSB

Example 2
IN :  [0xFF, 0x00, 0xAA, 0x55]  
OUT: [0x55, 0x55, 0xAA, 0xAA, 0x66, 0x66, 0x99, 0x99]

Example 3
IN : [0x12, 0x34, 0x56, 0x78, 0x90]  
OUT: [0xA6, 0xA9, 0x9A, 0xA5, 0x96, 0x99, 0x6A, 0x95, 0xAA, 0x69] 

Example 4
IN : [0x01, 0x02, 0x03, 0xF1, 0xF2, 0xF3]  
OUT: [0xA9, 0xAA, 0xA6, 0xAA, 0xA5, 0xAA, 0xA9, 0x55, 0xA6, 0x55, 0xA5, 0x55]

reglas :

• La solución solo requiere un algoritmo para convertir la entrada en salida.
• La adquisición de entrada y salida de impresión NO son una parte necesaria de la solución, pero pueden incluirse. Le recomendamos que proporcione su código de prueba / impresión si no está incluido en su solución.
• La entrada es una matriz de bytes de 8 bits (lo que sea que eso signifique en el idioma que elija), NO una cadena de texto. Puede usar cadenas como formato de almacenamiento si es conveniente en su idioma, pero se deben admitir caracteres no imprimibles (es decir, 0xFF). La entrada también puede tomar una longitud si es necesario.
• La memoria para la salida debe ser asignada por su rutina, no proporcionada. editar: requisito innecesario
• La salida también es una matriz de bytes de 8 bits, y una longitud si es necesario.
• Debe admitir al menos 16 KB de entrada
• El rendimiento no debe ser demasiado horrible: <10 segundos por 16 KB
• Byte menos significativo primero en la memoria.

Desafío de canal lateral :

• ¡Desafíe la respuesta de otro usuario demostrando que su código es más rápido, más eficiente en memoria o produce un binario más pequeño!

¡A jugar golf! ¡El código más corto gana!

GolfScript 28 caracteres

{2{base}:|~4|43691-~256|~\}%

Versión equivalente sin optimización ofuscante:

{2base 4base 43691-~256base~\}%

El código acepta la entrada como una matriz de enteros y devuelve lo mismo.

Para cada número en la matriz, el número se convierte a la forma de la matriz de base 2, luego se convierte de nuevo en un número como si fuera la base 4, esto tiene el efecto de espaciar los bits con un 0 entre cada uno. 43691 luego se resta del número, y el resultado es binario invertido, esto es equivalente a restar el número de 43690 (43690 = 0b1010101010101010). El número se divide en dos partes al convertirlo en una matriz base 256, la matriz se descompone y se invierte el orden de los dos números resultantes.

Entrada de ejemplo:

[1 2 3 241 242 243]

Salida de ejemplo:

[169 170 166 170 165 170 169 85 166 85 165 85]

c - 224 caracteres

Creo que esto es funcional, incluida la asignación de requisitos de memoria desde que cayó.

#include <stdlib.h>
int B(char i){int16_t n,o=0xFFFF;for(n=0;n<8;++n)o^=((((i>>n)&1)+1))<<(2*n);
return o;}char* M(char*i,int n){char*o=calloc(n+1,2),*p=o;do{int r=B(*i++);
*p++=0xFF&r;*p++=(0xFF00&r)>>8;}while(--n);return o;}

La parte funcional del código es un bucle sobre los bits de cada carácter, observando que ((bit + 1) exclusivo-o 3) es el par de bits de salida, y aplica mucha lógica de desplazamiento y enmascaramiento para alinear todo.

Como es habitual en c, funciona en los datos como caracteres. El andamio de prueba no aceptará 0 bytes (porque c los trata como un final de cadena), pero el código de trabajo no tiene esa limitación.

Se podría jugar un poco más al copiar el trabajo de conversión de bytes en línea.

Prueba de funcionamiento (con andamio de prueba mejorado):

$ gcc -g manchester_golf.c
$ ./a.out AB xyz U
'AB':
[ 0x41, 0x42 ]
[ 0xa9, 0x9a, 0xa6, 0x9a ]
'xyz':
[ 0x78, 0x79, 0x7a ]
[ 0x6a, 0x95, 0x69, 0x95, 0x66, 0x95 ]
'U':
[ 0x55 ]
[ 0x99, 0x99 ]

Comentado, menos dependiente de la máquina y con andamio de prueba

/* manchester.c
 *
 * Manchester code a bit stream least significant bit first
 *
 * Manchester coding means that bits are expanded as {0,1} --> {10, 01}
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <stdint.h>
#include <string.h>

/* Caller must insure that out points to a valid, writable two byte
   buffer filled with 0xFF */
int16_t manByte(char i){
  int16_t n,o=0xFFFF;
  printf("Manchester coding byte 0x%hx...\n",i);
  for(n=0; n<CHAR_BIT; ++n)
    o ^= (
      (
       (
        (i>>n)&1) /* nth bit of i*/
       +1) /* +1 */
      ) <<(2*n) /* shifted up 2*n bits */ 
      ;
  printf("\tas 0x%hx\n",o);
  return o;
}

char* manBuf(const char*i, int n){
  char*o=calloc(n+1,2),*p=o;
  do{
    int16_t r=manByte(*i++);
    *p++= 0xFF&r;
    *p++=(0xFF00&r)>>8;
  } while(--n);
  return o;
}

void pbuf(FILE* f, char *buf, int len){
  int i;
  fprintf(f,"[");
  for(i=0; i<len-1; i++)
    fprintf(f," 0x%hhx,",buf[i]);
  fprintf(f," 0x%hhx ]\n",buf[len-1]);
}

int main(int argc, char**argv){
  int i;
  for(i=1; i<argc; i++){
    int l=strlen(argv[i]);
    char *o=manBuf(argv[i],l);
    printf("'%s':\n",argv[i]);
    pbuf(stdout,argv[i],l);
    pbuf(stdout,o,l*2);
    free(o);
  }
  return 0;
}

J, 36

,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)

Esquema de explicación (Ver vocabulario J para referencia):

• ,@:(3 :'...'"0)aplica el ... a cada entrada "byte" como y, dando como resultado dos bytes (enteros) cada uno. El resultado es aplanado por ,.
• y#:~8#2es equivalente a 2 2 2 2 2 2 2 2 #: y, o vector de los 8 dígitos de base 2 menos significativos de y.
• 4|. intercambia el frente y la parte posterior 4 bits girando 4 posiciones.
• (,.~-.)es equivalente 3 :'(-. y) ,. y'o no al argumento 'cosido' al argumento (tomando forma 8 2).
• #.2 8$, aplana el resultado dando el flujo de bits, da nueva forma a 2 filas de 8 y convierte desde la base 2.

Ejemplo de uso (J, interactivo):

    ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0) 1 2 3 241 242 243
,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0) 1 2 3 241 242 243
169 170 166 170 165 170 169 85 166 85 165 85

Información de velocidad (J, interactiva):

   manchester =: ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)
manchester =: ,@:(3 :'#.2 8$,(,.~-.)4|.y#:~8#2'"0)
   data =: 256 | i. 16384
data =: 256 | i. 16384
   100 (6!:2) 'manchester data'
100 (6!:2) 'manchester data'
0.243138

El tiempo medio para 16kb es de menos de .25s, Intel Core Duo 1.83Ghz o similar.

Haskell, 76 personajes

import Bits
z a=170-sum[a.&.p*p|p<-[1,2,4,8]]
y a=[z a,z$a`div`16]
m=(>>=y)

Pruebas de funcionamiento:

> testAll 
input      [10, 02]
encoded    [AA, A9, A6, AA]
  pass
input      [FF, 00, AA, 55]
encoded    [55, 55, AA, AA, 66, 66, 99, 99]
  pass
input      [12, 34, 56, 78, 90]
encoded    [A6, A9, 9A, A5, 96, 99, 6A, 95, AA, 69]
  pass
input      [01, 02, 03, F1, F2, F3]
encoded    [A9, AA, A6, AA, A5, AA, A9, 55, A6, 55, A5, 55]
  pass

El rendimiento está dentro de las especificaciones. a 1MB en ~ 1.2s en mi laptop antigua. Sufre porque la entrada se convierte ay desde una lista, en lugar de procesarse como a ByteArray.

> dd bs=1m count=1 if=/dev/urandom | time ./2040-Manchester > /dev/null
1+0 records in
1+0 records out
1048576 bytes transferred in 1.339130 secs (783028 bytes/sec)
        1.20 real         1.18 user         0.01 sys

La fuente, 2040-Manchester.hs , incluye el código, las pruebas y la función principal para un filtro de línea de comando.

OCaml + Batteries, 138117 caracteres

let m s=Char.(String.(of_enum[?chr(170-Enum.sum[?d land
p*p|p<-List:[1;2;4;8]?])|c<-enum s/@code;d<-List:[c;c/16]?]))

Pruebas:

Con

let hex s = String.(enum s/@(Char.code|-Printf.sprintf "%02x")|>List.of_enum|>join" ")

Los resultados son:

m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x10\x02" |> hex;;
- : string = "aa a9 a6 aa"
m "\xFF\x00\xAA\x55" |> hex;;
- : string = "55 55 aa aa 66 66 99 99"
m "\x12\x34\x56\x78\x90" |> hex;;
- : string = "a6 a9 9a a5 96 99 6a 95 aa 69"
m "\x01\x02\x03\xF1\xF2\xF3" |> hex;;  
- : string = "a9 aa a6 aa a5 aa a9 55 a6 55 a5 55"

Como punto de referencia, con:

let benchmark n =
  let t = Unix.gettimeofday() in
  assert(2*n == String.(length (m (create n))));
  Unix.gettimeofday() -. t

Yo obtengo:

# benchmark 16_384;;
- : float = 0.115520954132080078

en mi MacBook

Python, 87 caracteres

Mes la función solicitada en el problema. Llama Na cada nybble y divide todo en una lista.

N=lambda x:170-(x&1|x*2&4|x*4&16|x*8&64)
M=lambda A:sum([[N(a),N(a>>4)]for a in A],[])

print map(hex,M([0x10,0x02]))
print map(hex,M([0xff,0x00,0xaa,0x55]))
print map(hex,M([0x12, 0x34, 0x56, 0x78, 0x90]))
print map(hex,M([0x01, 0x02, 0x03, 0xF1, 0xF2, 0xF3]))

genera

['0xaa', '0xa9', '0xa6', '0xaa']
['0x55', '0x55', '0xaa', '0xaa', '0x66', '0x66', '0x99', '0x99']
['0xa6', '0xa9', '0x9a', '0xa5', '0x96', '0x99', '0x6a', '0x95', '0xaa', '0x69']
['0xa9', '0xaa', '0xa6', '0xaa', '0xa5', '0xaa', '0xa9', '0x55', '0xa6', '0x55', '0xa5', '0x55']

APL (Dyalog Extended) , 22 bytes

∊(⌽(2⍴256)⊤43690-4⊥⊤)¨

Pruébalo en línea!

Puerto de la respuesta GolfScript.

∊(⌽(2⍴256)⊤43690-4⊥⊤)¨       Monadic train:
  ⌽(2⍴256)⊤43690-4⊥⊤         Define a helper function taking an integer n:
                    ⊤           Convert n to base 2. Monadic ⊤ is an Extended feature.
                  4⊥            Convert the result from base 4.
                                This puts the 1 digits of n 
                                in odd indices of the intermediate result.
            43960-              Subtract from 43690.
    (2⍴256)⊤                    Convert to 2 base-256 digits, corresponding to
                                nibbles of n.
  ⌽                            Reverse the order of these bytes.
 (                   )¨       Call the helper function for each element of the input
∊                             and flatten the results into a list.

C, 164 bytes

Toma una serie de bytes hexadecimales y los convierte a flujo binario de Manchester.

#include <stdio.h>
main(int c,char **v){int i,b,x,j=0;while(++j<c{sscanf(v[j],"%x",&b);x=b^0xff;for(i=9;--i;){printf("%d%d",x&1,b&1);x=x>>1;b=b>>1;}printf("\n");}}

#include <stdio.h>
main(int c,char **v){
int i,b,x,j=0;
while(++j<c){
    sscanf(v[j],"%x",&b);
    x=b^0xff;
    for(i=9;--i;){
        printf("%d%d",x&1,b&1);
        x=x>>1;b=b>>1;}
    printf("\n");}}

Prueba:

./a.out 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0

Salida:

1010101010101010
0110101010101010
1001101010101010
0101101010101010
1010011010101010
0110011010101010
1001011010101010
0101011010101010
1010100110101010
0110100110101010
1001100110101010
0101100110101010
1010010110101010
0110010110101010
1001010110101010
0101010110101010
1010101010101010
1010101001101010
1010101010011010
1010101001011010
1010101010100110
1010101001100110
1010101010010110
1010101001010110
1010101010101001
1010101001101001
1010101010011001
1010101001011001
1010101010100101
1010101001100101
1010101010010101
1010101001010101

Generador de conjunto de datos de prueba de 16 kb:

test_data.c:

#include <stdio.h>
void main()
{
int i=16*1024;
while(i--)
{
    printf("0x%02x ", i&0xFF);
}
printf("\n");
}

cc test_data.c -o test_data

Contrarreloj de núcleo 1.6G i5dual:

time ./a.out `./test_data` > test.out 
real    0m0.096s
user    0m0.090s
sys 0m0.011s

PHP, 156 bytes

function f($i){foreach($i as$n){$b=str_split(str_replace([0,1,2],[2,'01',10],
str_pad(decbin($n),8,0,0)),8);$o[]=bindec($b[1]);$o[]=bindec($b[0]);}return$o;}

Dada la entrada [0, 1, 2, 3, 4, 5], devuelve:

[170, 170, 169, 170, 166, 170, 165, 170, 154, 170, 153, 170]

Codifica 16 KiB de datos en 0.015 segundos y 1 MiB de datos en aproximadamente 0.9 segundos.

El código no protegido, otra implementación (más larga y aproximadamente dos veces más lenta) y los casos de prueba se pueden encontrar en mi página de soluciones de código de golf en Github.