Le codage Manchester est un protocole de télécommunications utilisé dans les communications radio qui garantit des transitions de bits à un intervalle régulier afin qu'un récepteur puisse récupérer la fréquence d'horloge à partir des données elles-mêmes. Il double le débit binaire, mais est bon marché et simple à mettre en œuvre. Il est largement utilisé par les opérateurs de radio amateur.

Le concept est très simple: au niveau matériel, l'horloge et les lignes de données sont simplement XOR ensemble. Dans le logiciel, cela est décrit comme convertissant un flux d'entrée de bits en un flux de sortie à double débit, chaque entrée «1» étant traduite en «01» et chaque entrée «0» traduite en «10».

C'est un problème facile, mais ouvert à de nombreuses implémentations en raison de sa nature bitstream. Autrement dit, le codage est conceptuellement un processus bit par bit au lieu d'un processus octet par octet. Nous sommes donc tous d'accord sur l'endianité, les bits les moins significatifs de l'entrée deviennent l'octet le moins significatif de la sortie.

Le temps du golf! Écrivez une fonction qui, étant donné un tableau d'octets de longueur arbitraire, retourne un tableau de ce gestionnaire de données codé.

L'entrée et la sortie doivent être considérées comme peu endiennes, l'octet le moins significatif en premier et le BIT le moins significatif en premier dans le flux binaire.

Dessin de flux binaire 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

Exemples :

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]

Règles :

• La solution ne nécessite qu'un algorithme pour convertir l'entrée en sortie.
• L'acquisition d'entrée et de sortie d'impression NE fait PAS partie de la solution, mais peut être incluse. Nous vous encourageons à fournir votre code de test / d'impression s'il n'est pas inclus dans votre solution.
• L'entrée est un tableau d'octets de 8 bits (quoi que cela puisse signifier dans la langue de votre choix), PAS une chaîne de texte. Vous pouvez utiliser des chaînes comme format de stockage si cela vous convient dans votre langue, mais les caractères non imprimables (c'est-à-dire 0xFF) doivent être pris en charge. L'entrée peut également prendre une longueur si nécessaire.
• La mémoire de sortie doit être allouée par votre routine, non fournie. modifier: exigence inutile
• La sortie est également un tableau d'octets de 8 bits et une longueur si nécessaire.
• Doit prendre en charge au moins 16 Ko d'entrée
• Les performances ne doivent pas être trop horribles: <10s pour 16 Ko
• Octet le moins significatif en premier en mémoire.

Défi du canal latéral :

• Défiez la réponse d'un autre utilisateur en prouvant que votre code est plus rapide, plus efficace en mémoire ou produit un binaire plus petit!

Faites du golf! Le code le plus court gagne!

GolfScript 28 caractères

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

Version équivalente sans optimisation obscurcissante:

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

Le code accepte l'entrée comme un tableau d'entiers et renvoie idem.

Pour chaque nombre dans le tableau, le nombre est converti en forme de tableau en base 2, il est ensuite reconverti en un nombre comme s'il s'agissait de la base 4, ce qui a pour effet d'espacer les bits avec un 0 entre chacun. 43691 est ensuite soustrait du nombre, et le résultat est binaire inversé, ce qui équivaut à soustraire le nombre de 43690 (43690 = 0b1010101010101010). Le nombre est ensuite divisé en deux parties en le convertissant en un tableau de base 256, le tableau est décomposé et l'ordre des deux nombres résultants est inversé.

Exemple d'entrée:

[1 2 3 241 242 243]

Exemple de sortie:

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

c - 224 caractères

Je crois que cela est fonctionnel, y compris l'allocation de mémoire requise depuis abandonné.

#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 partie de travail du code est une boucle sur les bits de chaque caractère, notant que ((bit + 1) exclusif ou 3) est la paire de bits de sortie, et appliquant beaucoup de logique de décalage et de masquage pour que tout soit aligné.

Comme c'est l'habitude de c, cela fonctionne sur les données sous forme de caractères. L'échafaudage de test n'acceptera pas 0 octet (car c les traite comme une fin de chaîne), mais le code de travail n'a pas une telle limitation.

Il pourrait être joué un peu plus en copiant le travail de conversion d'octets en ligne.

Test (avec échafaudage de test amélioré):

$ 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 ]

Commenté, moins dépendant de la machine et avec échafaudage de test

/* 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)

Aperçu de l'explication (voir le vocabulaire J pour référence):

• ,@:(3 :'...'"0)applique le ... à chaque "octet" d'entrée comme y, résultant en deux octets (entiers) chacun. Le résultat est aplati par ,.
• y#:~8#2est équivalent 2 2 2 2 2 2 2 2 #: you vecteur des 8 chiffres de base 2 les moins significatifs de y.
• 4|. échange les 4 bits avant et arrière en tournant de 4 positions.
• (,.~-.)est équivalent 3 :'(-. y) ,. y'ou non à l'argument «assemblé» à l'argument (prenant la forme 8 2).
• #.2 8$, aplatit le résultat en donnant le train de bits, remodèle à 2 rangées de 8 et convertit à partir de la base 2.

Exemple d'utilisation (J, interactif):

    ,@:(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

Informations de vitesse (J, interactif):

   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

Le temps moyen pour 16 Ko est un peu moins de 0,25 s, Intel Core Duo 1,83 GHz ou similaire.

Haskell, 76 caractères

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

Essais:

> 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

Les performances sont bien conformes aux spécifications. à 1 Mo en ~ 1,2 s sur mon portable ancien. Il souffre parce que l'entrée est convertie vers et depuis une liste, plutôt traitée comme un 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 source, 2040-Manchester.hs , inclut le code, les tests et la fonction principale d'un filtre de ligne de commande.

OCaml + Batteries, 138 117 caractères

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]?]))

Tests:

Avec

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

Les résultats sont:

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"

Comme référence, avec:

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

Je reçois:

# benchmark 16_384;;
- : float = 0.115520954132080078

sur mon MacBook.

Python, 87 caractères

Mest la fonction demandée dans le problème. Il appelle Nchaque nybble et regroupe tout en une liste.

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]))

génère

['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 octets

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

Essayez-le en ligne!

Port de la réponse 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 octets

Prend une série d'octets hexadécimaux et convertit en flux binaire 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");}}

Tester:

./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

Production:

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

Générateur de jeu de données de test de 16 Ko:

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

Contre-la-montre de base 1.6G i5dual:

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

PHP, 156 octets

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;}

Compte tenu de l'entrée [0, 1, 2, 3, 4, 5], il renvoie:

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

Il code 16 Ko de données en 0,015 seconde et 1 Mo de données en environ 0,9 seconde.

Le code non golfé, une autre implémentation (plus longue et environ deux fois plus lente) et les cas de test peuvent être trouvés sur ma page de solutions de golf de code sur Github.