Die Manchester-Codierung ist ein Telekommunikationsprotokoll, das in der Funkkommunikation verwendet wird und in regelmäßigen Abständen Bitübergänge garantiert, damit ein Empfänger die Taktrate aus den Daten selbst wiederherstellen kann. Es verdoppelt die Bitrate, ist aber billig und einfach zu implementieren. Es wird häufig von Amateurfunkern eingesetzt.

Das Konzept ist sehr einfach: Auf Hardware-Ebene werden die Takt- und Datenleitungen einfach XOR-verknüpft. In der Software wird dies so dargestellt, dass ein Eingabestrom von Bits in einen Ausgabestrom mit doppelter Rate umgewandelt wird, wobei jede Eingabe "1" in eine "01" und jede Eingabe "0" in eine "10" übersetzt wird.

Dies ist ein einfaches Problem, das aufgrund seines Bitstream-Charakters jedoch für viele Implementierungen offen ist. Das heißt, die Codierung ist konzeptionell ein bitweiser Prozess anstelle eines byteweisen Prozesses. Wir sind uns also alle einig, dass die niedrigstwertigen Bits der Eingabe das niedrigstwertige Byte der Ausgabe sind.

Zeit zum Golfen! Schreiben Sie eine Funktion, die bei einem Array mit beliebiger Länge von Bytes ein Array der nach Manchester codierten Daten zurückgibt.

Eingabe und Ausgabe sollten als Little-Endian, niedrigstwertiges Byte zuerst und niedrigstwertiges BIT zuerst im Bitstrom betrachtet werden.

ASCII - Bitstrom Zeichnung :

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

Beispiele :

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]

Regeln :

• Die Lösung erfordert nur einen Algorithmus, um die Eingabe in die Ausgabe umzuwandeln.
• Erfassen von Eingaben und Drucken von Ausgaben sind KEIN erforderlicher Teil der Lösung, können jedoch enthalten sein. Sie werden aufgefordert, Ihren Test- / Druckcode anzugeben, wenn dieser nicht in Ihrer Lösung enthalten ist.
• Die Eingabe ist ein Array von 8-Bit-Bytes (was auch immer dies in der Sprache Ihrer Wahl bedeuten mag), KEINE Textzeichenfolge. Sie können Zeichenfolgen als Speicherformat verwenden, wenn dies in Ihrer Sprache zweckmäßig ist. Nicht druckbare Zeichen (z. B. 0xFF) müssen jedoch unterstützt werden. Bei Bedarf kann die Eingabe auch eine Länge haben.
• Der Speicher für die Ausgabe muss von Ihrer Routine zugewiesen werden und wird nicht bereitgestellt. edit: unnötige anforderung
• Die Ausgabe erfolgt ebenfalls in einem Array von 8-Bit-Bytes und bei Bedarf in einer Länge.
• Müssen mindestens 16KB Eingang unterstützen
• Die Leistung darf nicht zu schlecht sein: <10s für 16KB
• Das niedrigstwertige Byte zuerst im Speicher.

Seitenkanal-Herausforderung :

• Fordern Sie die Antwort eines anderen Benutzers heraus, indem Sie beweisen, dass Ihr Code schneller und speichereffizienter ist oder eine kleinere Binärdatei erzeugt!

Golf spielen! Kürzester Code gewinnt!

GolfScript 28 Zeichen

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

Äquivalente Version ohne verschleierte Optimierung:

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

Der Code akzeptiert Eingaben als Array von Ganzzahlen und gibt dasselbe zurück.

Für jede Zahl in dem Array wird die Zahl in die Matrixform zur Basis 2 konvertiert, dann wird sie zurück in eine Zahl konvertiert, als ob es die Basis 4 wäre. Dies hat den Effekt, dass die Bits mit einer 0 dazwischen beabstandet werden. 43691 wird dann von der Zahl subtrahiert, und das Ergebnis wird binär invertiert. Dies entspricht dem Subtrahieren der Zahl von 43690 (43690 = 0b10101010101010). Die Zahl wird dann in zwei Teile geteilt, indem sie in ein Basis-256-Array umgewandelt wird, das Array wird zerlegt und die Reihenfolge der beiden resultierenden Zahlen wird invertiert.

Beispiel Eingabe:

[1 2 3 241 242 243]

Beispielausgabe:

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

c - 224 Zeichen

Ich glaube, dass dies funktioniert, einschließlich der Zuordnung des Speicherbedarfs, der seither entfällt.

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

Der funktionierende Teil des Codes ist eine Schleife über die Bits jedes Zeichens, wobei zu beachten ist, dass ((bit + 1) exclusive-or 3) das Ausgangsbitpaar ist, und viel Verschiebungs- und Maskierungslogik angewendet wird, um alles in eine Linie zu bringen.

Wie bei c üblich, werden die Daten als Zeichen verarbeitet. Das Testgerüst akzeptiert keine 0 Bytes (weil c sie als String-Endung behandelt), aber der Arbeitscode unterliegt keiner solchen Einschränkung.

Wenn Sie die Byte-Konvertierungsarbeit inline kopieren, wird möglicherweise etwas mehr Golf gespielt.

Testlauf (mit verbessertem Testgerüst):

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

Kommentiert, weniger maschinenabhängig und mit Testgerüst

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

Erklärung (Siehe J Vokabular als Referenz):

• ,@:(3 :'...'"0)Wendet das ... auf jedes Eingabe- "Byte" als y an, was jeweils zwei Bytes (ganze Zahlen) ergibt. Das Ergebnis wird durch abgeflacht ,.
• y#:~8#2ist äquivalent zu 2 2 2 2 2 2 2 2 #: yoder Vektor der 8 niedrigstwertigen Basis-2-Stellen von y.
• 4|. Vertauscht die vorderen und hinteren 4 Bits durch Drehen um 4 Positionen.
• (,.~-.)entspricht 3 :'(-. y) ,. y'oder nicht dem Argument, das mit dem Argument „verbunden“ ist (nimmt die Form 8 2 an).
• #.2 8$, Verflacht das Ergebnis mit dem Bitstream, formt sich in 2 8er-Zeilen um und konvertiert von Basis 2.

Anwendungsbeispiel (J, interaktiv):

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

Geschwindigkeitsinformationen (J, interaktiv):

   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

Die durchschnittliche Zeit für 16 KB beträgt knapp 0,25 s, Intel Core Duo 1,83 GHz oder ähnliches.

Haskell, 76 Zeichen

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

Testläufe:

> 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

Die Leistung entspricht den Spezifikationen. bei 1 MB in ~ 1,2 s auf meinem alten Laptop. Es leidet, weil die Eingabe in und aus einer Liste konvertiert und dann als eine verarbeitet wird 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

Die Quelle 2040-Manchester.hs enthält den Code, die Tests und die Hauptfunktion für einen Befehlszeilenfilter.

OCaml + Batterien, 138 117 Zeichen

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:

Mit

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

Die Ergebnisse sind:

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"

Als Benchmark mit:

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

Ich bekomme:

# benchmark 16_384;;
- : float = 0.115520954132080078

auf meinem MacBook.

Python, 87 Zeichen

Mist die im Problem angeforderte Funktion. Es ruft Nnach jedem Nybble auf und fügt alles wieder in eine Liste ein.

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

erzeugt

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

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

Probieren Sie es online!

Port der GolfScript-Antwort.

∊(⌽(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

Nimmt eine Reihe von hexadezimalen Bytes auf und konvertiert sie in einen Manchester-Binärdatenstrom.

#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");}}

Prüfung:

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

Ausgabe:

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

16kb Testdatensatz Generator:

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

1.6G i5dual Core Zeitfahren:

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

Bei der Eingabe [0, 1, 2, 3, 4, 5]wird Folgendes zurückgegeben:

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

Es codiert 16 KB Daten in 0,015 Sekunden und 1 MB Daten in etwa 0,9 Sekunden.

Den ungolfed Code, eine weitere Implementierung (länger und ungefähr zweimal langsamer) und die Testfälle finden Sie auf meiner Code-Golf-Lösungsseite bei Github.