[dorkbotpdx-blabber] The puzzle answer is Morse Code

23 views
Skip to first unread message

David Turnbull

unread,
Apr 9, 2013, 1:54:42 AM4/9/13
to A discussion list for dorkbot-pdx (portland, or)
Everything in Morse Code, as defined by the ITU, is six dots and dashes or less. Six bits can easily represent this data but you also need a length. It takes three bits to store lengths of 1-6. If we assign special usage of the length 0 then we can overlap one of the bits and store the whole thing in a single 8-bit word. Length 7 is used to indicate no morse code is available. The usual method for an 8-bit morse code table will mark the start of the code with a 1. You shift the byte and calculate the length by subtracting 1 starting from 8 until the first 1 falls off. My technique is faster; all you do is mask off the length and change it to 6 if it's a zero. Plus, I have a nifty macro that lets you write dash-dash-dot-dash as MCODE(3313) instead of a cryptic "0x1D". Dashes are 3 times as long as a dot, so this is quite reasonable.

Information about the classic solution can be found here: http://kb8ojh.net/msp430/morse_encoding.html

The entire program follows. It can easily be modified for Arduino or anything with a C compiler. Simply change the two lines that turn the LED on and off and follow the usage example.


// Copyright 2013 David Turnbull AE9RB
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include <device.h>

// MCODE is an 8-bit-per-chararcter morse code encoding macro.
// Dots are represented as 1s; dashs are 3s. The length is stored in the three
// lowest bits. Dots are encoded as binary 0; dashes are 1; left aligned.
// For example, letter Q is encoded as "1101" plus a filler "0" then "100".
// The astute bit twiddler will notice that bit 0x40 is part of both
// the code and length; a stored length of 0 is interpreted as 6.
// Use MCODE(0) to indicate a character with no valid morse code.
// These invalid characters will have a stored length of 7.
#define MCODE_L(x) (((x&0x0000000FLU)?1:0)\
+((x&0x000000F0LU)?1:0)\
+((x&0x00000F00LU)?1:0)\
+((x&0x0000F000LU)?1:0)\
+((x&0x000F0000LU)?1:0)\
+((x&0x00F00000LU)?1:0))
#define MCODE_C(x) (((x&0x00000002LU)?1:0)\
+((x&0x00000020LU)?2:0)\
+((x&0x00000200LU)?4:0)\
+((x&0x00002000LU)?8:0)\
+((x&0x00020000LU)?16:0)\
+((x&0x00200000LU)?32:0))
#define MCODE_6(x) (((x&0x00F00000LU)?4:0)\
+ ((((x&0x00F00000LU)?1:0) & ((x&0x00000002LU)?0:1))?2:0))
#define MCODE(d)((uint8) (d==0)?7:MCODE_L(0x##d##LU)\
+ (MCODE_C(0x##d##LU) << 8 - MCODE_L(0x##d##LU))\
- MCODE_6(0x##d##LU))

const uint8 code MCODES[] = {
    /* 0x22 " */ MCODE(131131),
    /* 0x23 # */ MCODE(0),
    /* 0x24 $ */ MCODE(0),
    /* 0x25 % */ MCODE(0),
    /* 0x26 & */ MCODE(0),
    /* 0x27 ' */ MCODE(133331),
    /* 0x28 ( */ MCODE(31331),
    /* 0x29 ) */ MCODE(313313),
    /* 0x2A * */ MCODE(0),
    /* 0x2B + */ MCODE(13131),
    /* 0x2C , */ MCODE(331133),
    /* 0x2D - */ MCODE(311113),
    /* 0x2E . */ MCODE(131313),
    /* 0x2F / */ MCODE(31131),
    /* 0x30 0 */ MCODE(33333),
    /* 0x31 1 */ MCODE(13333),
    /* 0x32 2 */ MCODE(11333),
    /* 0x33 3 */ MCODE(11133),
    /* 0x34 4 */ MCODE(11113),
    /* 0x35 5 */ MCODE(11111),
    /* 0x36 6 */ MCODE(31111),
    /* 0x37 7 */ MCODE(33111),
    /* 0x38 8 */ MCODE(33311),
    /* 0x39 9 */ MCODE(33331),
    /* 0x3A : */ MCODE(333111),
    /* 0x3B ; */ MCODE(0),
    /* 0x3C < */ MCODE(0),
    /* 0x3D = */ MCODE(31113),
    /* 0x3E > */ MCODE(0),
    /* 0x3F ? */ MCODE(113311),
    /* 0x40 @ */ MCODE(133131),
    /* 0x41 A */ MCODE(13),
    /* 0x42 B */ MCODE(3111),
    /* 0x43 C */ MCODE(3131),
    /* 0x44 D */ MCODE(311),
    /* 0x45 E */ MCODE(1),
    /* 0x46 F */ MCODE(1131),
    /* 0x47 G */ MCODE(331),
    /* 0x48 H */ MCODE(1111),
    /* 0x49 I */ MCODE(11),
    /* 0x4A J */ MCODE(1333),
    /* 0x4B K */ MCODE(313),
    /* 0x4C L */ MCODE(1311),
    /* 0x4D M */ MCODE(33),
    /* 0x4E N */ MCODE(31),
    /* 0x4F O */ MCODE(333),
    /* 0x50 P */ MCODE(1331),
    /* 0x51 Q */ MCODE(3313),
    /* 0x52 R */ MCODE(131),
    /* 0x53 S */ MCODE(111),
    /* 0x54 T */ MCODE(3),
    /* 0x55 U */ MCODE(113),
    /* 0x56 V */ MCODE(1113),
    /* 0x57 W */ MCODE(133),
    /* 0x58 X */ MCODE(3113),
    /* 0x59 Y */ MCODE(3133),
    /* 0x5A Z */ MCODE(3311),
};

#define MORSE_DOT  1
#define MORSE_DASH 3
#define MORSE_CHAR 3
#define MORSE_WORD 7

// Example usage:
// Morse_Main("Repeating Message ");for(;;){sleep(240);Morse_Main(0);}
void Morse_Main(char* msg) {
    static uint8 pos, codes, len, state, timer, *message;
    uint8 i;

    if (msg) {
        state = pos = 0;
        message = msg;
    }
    else switch (state) {
    case 0:
        if (!message[pos]) pos = 0;
        i = message[pos++];
        if (i >= 0x61 && i <= 0x7A) i -= 32;
        if (i < 0x22 || i > 0x5A) codes = 7;
        else codes = MCODES[i-0x22];
        len = codes & 0x07;
        if (len==0) len = 6;
        if (codes==7) {
            timer = MORSE_WORD - MORSE_CHAR - 2;
            len = 0;
            state = 3;
            break;
        }
    case 1:
        if (codes & 0x80) timer = MORSE_DASH;
        else timer = MORSE_DOT;
        codes <<= 1;
        len--;
        Control_Write(Control_Read() & ~CONTROL_LED);
        state = 2;
    case 2:
        if (!timer) {
            state = 3;
            if (!len) timer = MORSE_CHAR - 1;
            else timer = MORSE_DOT - 1;
            Control_Write(Control_Read() | CONTROL_LED);
        }
        else {
            timer--;
            break;
        }
    case 3:
        if (!timer) {
            if (!len) state = 0;
            else state = 1;
        }
        else timer--;
    }
}

Neal

unread,
Apr 9, 2013, 2:14:01 AM4/9/13
to A discussion list for dorkbot-pdx (portland, or)
Interesting information David. Any reason you didn't start with ! instead of "?

I ask because I had to look up ! a couple days ago, my CW days being long long past. Apparently there's no universal answer. I elected to go with 313133, per your macros.

NealS

David Turnbull

unread,
Apr 9, 2013, 3:08:42 AM4/9/13
to A discussion list for dorkbot-pdx (portland, or)
On Mon, Apr 8, 2013 at 11:14 PM, Neal <nse...@gmail.com> wrote:
Interesting information David. Any reason you didn't start with ! instead of "?

I simply followed ITU Recommendation M.1677-1 which has no ! character. I only need letters and number for my application. Following the full ITU recommendation solved problems I didn't have but seemed reasonable since it only cost 16 more bytes of ROM. Adding a bunch of non-standard characters would have been frivolous, but you should certainly add them if you have the need.

-david

Doug Ausmus

unread,
Apr 9, 2013, 11:04:33 AM4/9/13
to A discussion list for dorkbot-pdx (portland, or)
Very cool... had me fooled. The instant I read 'Morse Code", it became clear. Nice. :-)
Doug


_______________________________________________
dorkbotpdx-blabber mailing list
dorkbotpd...@dorkbot.org
http://music.columbia.edu/mailman/listinfo/dorkbotpdx-blabber

David Madden

unread,
Apr 9, 2013, 11:11:11 AM4/9/13
to A discussion list for dorkbot-pdx (portland, or)
On 4/8/2013 22:54, David Turnbull wrote:
> Everything in Morse Code

Insane. (At least without the comments!)

Reminds me of the International Obfuscated C Contest, where Morse code
is a recurring theme. For example:

http://www.cise.ufl.edu/~manuel/obfuscate/hague

#define DIT (
#define DAH )
#define __DAH ++
#define DITDAH *
#define DAHDIT for
#define DIT_DAH malloc
#define DAH_DIT gets
#define _DAHDIT char
_DAHDIT _DAH_[]="ETIANMSURWDKGOHVFaLaPJBXCYZQb54a3d2f16g7c8a90l?e'b.s;i,d:"
;main DIT DAH{_DAHDIT
DITDAH _DIT,DITDAH DAH_,DITDAH DIT_,
DITDAH _DIT_,DITDAH DIT_DAH DIT
DAH,DITDAH DAH_DIT DIT DAH;DAHDIT
DIT _DIT=DIT_DAH DIT 81 DAH,DIT_=_DIT
__DAH;_DIT==DAH_DIT DIT _DIT DAH;__DIT
DIT'\n'DAH DAH DAHDIT DIT DAH_=_DIT;DITDAH
DAH_;__DIT DIT DITDAH
_DIT_?_DAH DIT DITDAH DIT_ DAH:'?'DAH,__DIT
DIT' 'DAH,DAH_ __DAH DAH DAHDIT DIT
DITDAH DIT_=2,_DIT_=_DAH_; DITDAH _DIT_&&DIT
DITDAH _DIT_!=DIT DITDAH DAH_>='a'? DITDAH
DAH_&223:DITDAH DAH_ DAH DAH; DIT
DITDAH DIT_ DAH __DAH,_DIT_ __DAH DAH
DITDAH DIT_+= DIT DITDAH _DIT_>='a'? DITDAH _DIT_-'a':0
DAH;}_DAH DIT DIT_ DAH{ __DIT DIT
DIT_>3?_DAH DIT DIT_>>1 DAH:'\0'DAH;return
DIT_&1?'-':'.';}__DIT DIT DIT_ DAH _DAHDIT
DIT_;{DIT void DAH write DIT 1,&DIT_,1 DAH;}

--
Mersenne Law LLC · www.mersenne.com · +1-503-679-1671
- Small Business, Startup and Intellectual Property Law -
1500 SW First Ave. · Suite 1170 · Portland, Oregon 97201

Doug Ausmus

unread,
Apr 9, 2013, 11:43:51 AM4/9/13
to A discussion list for dorkbot-pdx (portland, or)
<LOL!>


On Tue, Apr 9, 2013 at 8:11 AM, David Madden <d...@mersenne.com> wrote:
On 4/8/2013 22:54, David Turnbull wrote:
> Everything in Morse Code

Insane.  (At least without the comments!)

Reminds me of the International Obfuscated C Contest, where Morse code
is a recurring theme.  For example:

http://www.cise.ufl.edu/~manuel/obfuscate/hague

#define DIT     (
<snip>
Reply all
Reply to author
Forward
0 new messages