Manchester encode a data stream

GolfScript 28 characters

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

Equivalent version without obfuscating optimization:

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

The code accept input as an array of integers, and return ditto.

For each number in the array the number is converted to base 2 array form, it is then converted back to a number as if it was base 4, this has the effect of spacing out the bits with a 0 in between each. 43691 is then subtracted from the number, and the result is binary inverted, this is equivalent to subtracting the number from 43690 (43690 = 0b1010101010101010). The number is then split into two parts by converting it to a base 256 array, the array is decomposed and the order of the two resulting numbers is inverted.

Example input:

[1 2 3 241 242 243]

Example output:

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

c -- 224 characters

I believe that this is functional, including the allocation of memory requirement since dropped.

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

The working part of the code is a loop over the bits of each character, noting that ((bit+1) exclusive-or 3) is the output bit pair, and applying lots of shifting and masking logic to get everything to line up.

As is c's wont, it works on the data as characters. The test scaffold won't accept 0 bytes (because c treats them as string ending), but the working code has no such limitation.

It might be golfed little more by copy the byte conversion work inline.

Test run (with improved test scaffold):

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

Commented, less machine dependent, and with test scaffold

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

Outline of explanation (See J Vocabulary for reference):

• ,@:(3 :'...'"0) applies the ... to each input "byte" as y, resulting in two bytes (integers) each. The result is flattened by ,.
• y#:~8#2 is equivalent to 2 2 2 2 2 2 2 2 #: y, or vector of the 8 least significant base-2 digits of y.
• 4|. swaps the front and back 4 bits by rotating by 4 positions.
• (,.~-.) is equivalent to 3 :'(-. y) ,. y', or not of the argument 'stitched' to the argument (taking on shape 8 2).
• #.2 8$, flattens the result giving the bitstream, reshapes to 2 rows of 8, and converts from base 2.

Example usage (J, interactive):

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

Speed information (J, interactive):

   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

Mean time for 16kb is just under .25s, Intel Core Duo 1.83Ghz or similar.