Kodowanie Manchester jest protokołem telekomunikacyjnym stosowanym w komunikacji radiowej, który gwarantuje przejścia bitów w regularnych odstępach czasu, dzięki czemu odbiornik może odzyskać częstotliwość zegara z samych danych. Podwaja przepływność, ale jest tani i prosty do wdrożenia. Jest szeroko stosowany przez amatorskich operatorów radiowych.

Pomysł jest bardzo prosty: na poziomie sprzętowym zegar i linie danych są po prostu XOR razem. W oprogramowaniu jest to przedstawiane jako przekształcanie strumienia wejściowego bitów w strumień wyjściowy o podwójnej szybkości, z każdym wejściowym „1” przetłumaczonym na „01” i każdym wejściowym „0” przetłumaczonym na „10”.

Jest to prosty problem, ale otwarty na wiele implementacji ze względu na swój charakter strumienia bitów. Oznacza to, że kodowanie jest koncepcyjnie procesem krok po kroku zamiast procesu bajt po bajcie. Wszyscy zgadzamy się co do endianowości, najmniej znaczące bity wejściowe stają się najmniej znaczącym bajtem wyjściowym.

Czas na golfa! Napisz funkcję, która, biorąc pod uwagę dowolną długość tablicy bajtów, zwraca tablicę danych zakodowanych w Manchester.

Wejścia i wyjścia należy traktować jako little-endian, najpierw najmniej znaczący bajt, a najmniej znaczący BIT pierwszy w strumieniu bitów.

Rysunek strumienia bitów 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

Przykłady :

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]

Zasady :

• Rozwiązanie wymaga jedynie algorytmu do konwersji danych wejściowych na dane wyjściowe.
• Pozyskiwanie danych wejściowych i wyjściowych NIE jest wymaganą częścią rozwiązania, ale może zostać uwzględnione. Zachęcamy do podania kodu testowego / drukowanego, jeśli nie jest uwzględniony w rozwiązaniu.
• Dane wejściowe to tablica 8-bitowych bajtów (cokolwiek to może znaczyć w wybranym języku), a NIE ciąg tekstowy. Możesz użyć ciągów jako formatu pamięci, jeśli jest to wygodne w twoim języku, ale znaki niedrukowalne (tj. 0xFF) muszą być obsługiwane. W razie potrzeby dane wejściowe mogą również trwać długo.
• Pamięć wyjściowa musi być przydzielona przez twoją procedurę, a nie zapewniona. edycja: niepotrzebne wymagania
• Dane wyjściowe to także tablica 8-bitowych bajtów i długość, jeśli to konieczne.
• Musi obsługiwać co najmniej 16 KB wejścia
• Wydajność nie może być zbyt okropna: <10 s dla 16 KB
• Najmniej znaczący bajt jako pierwszy w pamięci.

Wyzwanie w kanale bocznym :

• Zmierz się z odpowiedzią innego użytkownika, udowadniając, że Twój kod jest szybszy, bardziej wydajny pod względem pamięci lub tworzy mniejszy plik binarny!

Zagraj w golfa! Najkrótszy kod wygrywa!

GolfScript 28 znaków

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

Wersja równoważna bez zaciemniającej optymalizacji:

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

Kod akceptuje dane wejściowe jako tablicę liczb całkowitych i zwraca to samo.

Dla każdej liczby w tablicy liczba jest konwertowana na postać macierzy podstawy 2, a następnie jest konwertowana z powrotem na liczbę, tak jakby to była podstawa 4, co powoduje rozstawianie bitów z 0 pomiędzy nimi. 43691 jest następnie odejmowane od liczby, a wynik jest odwracany binarnie, co jest równoważne odejmowaniu liczby od 43690 (43690 = 0b1010101010101010). Liczba jest następnie dzielona na dwie części przez przekształcenie jej w podstawową tablicę 256, tablica jest rozkładana i kolejność dwóch wynikowych liczb jest odwracana.

Przykładowe dane wejściowe:

[1 2 3 241 242 243]

Przykładowe dane wyjściowe:

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

c - 224 znaki

Uważam, że jest to funkcjonalne, w tym alokacja zapotrzebowania na pamięć od momentu jego utraty.

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

Działającą częścią kodu jest pętla nad bitami każdego znaku, zauważając, że ((bit + 1) wyłączny-lub 3) jest parą bitów wyjściowych i stosuje wiele logiki przesunięcia i maskowania, aby wszystko wyrównać.

Jak to zwykle bywa, działa on na danych jako znakach. Testowe rusztowanie nie przyjmuje 0 bajtów (ponieważ c traktuje je jako zakończenie łańcucha), ale działający kod nie ma takich ograniczeń.

Może być nieco bardziej golfa, kopiując wbudowaną konwersję bajtów.

Uruchomienie testowe (z ulepszonym rusztowaniem testowym):

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

Komentowany, mniej zależny od maszyny i z rusztowaniem testowym

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

Zarys wyjaśnienia (zob. J Słownictwo w celu odniesienia):

• ,@:(3 :'...'"0)stosuje ... do każdego wejściowego „bajtu” jako y, co daje dwa bajty (liczby całkowite) każdy. Wynik jest spłaszczony o, .
• y#:~8#2jest równoważne 2 2 2 2 2 2 2 2 #: ylub wektorze z 8 najmniej znaczących cyfr podstawowych 2 y.
• 4|. zamienia przednie i tylne 4 bity, obracając o 4 pozycje.
• (,.~-.)jest równoważne 3 :'(-. y) ,. y'argumentowi „zszytemu” z argumentem (przybierając kształt 8 2) lub nie.
• #.2 8$, spłaszcza wynik, dając strumień bitów, przekształca go w 2 rzędy po 8 i konwertuje z podstawy 2.

Przykładowe użycie (J, interaktywne):

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

Informacje o prędkości (J, interaktywne):

   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

Średni czas dla 16 kb to niecałe 0,25 s, Intel Core Duo 1,83 Ghz lub podobny.

Haskell, 76 znaków

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

Przebiegi testowe:

> 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

Wydajność mieści się w zakresie specyfikacji. przy 1 MB w ~ 1,2 s na moim starym laptopie. Cierpi, ponieważ dane wejściowe są konwertowane na listę iz listy, a następnie przetwarzane jako 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

Źródło, 2040-Manchester.hs , zawiera kod, testy i główną funkcję filtru wiersza poleceń.

OCaml + Baterie, 138 117 znaków

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

Testy:

Z

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

Wyniki są następujące:

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"

Jako punkt odniesienia z:

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

Dostaję:

# benchmark 16_384;;
- : float = 0.115520954132080078

na moim MacBooku.

Python, 87 znaków

Mjest funkcją wymaganą w problemie. Wzywa Ndo każdego wątku i dzieli wszystko z powrotem na listę.

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

generuje

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

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

Wypróbuj online!

Port odpowiedzi 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 bajty

Pobiera szereg bajtów szesnastkowych i konwertuje na strumień binarny 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");}}

Test:

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

Wynik:

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

Generator zestawu danych testowych 16kb:

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 czas próbny rdzenia:

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

PHP, 156 bajtów

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

Biorąc pod uwagę dane wejściowe [0, 1, 2, 3, 4, 5], zwraca:

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

Koduje 16 KiB danych w 0,015 sekundy i 1 MiB danych w około 0,9 sekundy.

Niegolfowany kod, kolejna implementacja (dłuższa i około dwukrotnie wolniejsza) oraz przypadki testowe można znaleźć na mojej stronie rozwiązań do gry w golfa na Githubie.