001package jmri.jmrix.direct;
002
003/**
004 * Provide utilities for coding/decoding NMRA {@literal S&RP} DCC packets into
005 * sequences to send through a standard serial port.
006 * <p>
007 * This is strongly based on the makepckt.c file from the PacketScript 1.1.
008 * package of Kenneth Rice. The original header comment from that file follows
009 * here.
010 *
011 * <pre>
012 *
013 * Some Useful Background information
014 *
015 *      startbit: 1
016 *      stopbit : 1
017 *      databits: 8
018 *      baudrate: 19200
019 *
020 *      {@literal ==>} one serial bit takes 52.08 usec. (at 19200 baud)
021 *
022 *      {@literal ==>} NMRA-1-Bit: 01         (52 usec low and 52 usec high)
023 *          NMRA-0-Bit: 0011       (at least 100 usec low and high)
024 *           note we are allowed to stretch NMRA-0 e.g. 000111,
025 *           00001111, 000001111
026 *          are all valid NMRA-0 representations
027 *
028 *      serial stream (only start/stop bits):
029 *
030 *      0_______10_______10_______10_______10_______10_______10___ ...
031 *
032 *      problem: how to place the NMRA-0- and NMRA-1-Bits in the
033 *    serial stream
034 *
035 *     examples:
036 *
037 *      0          0xF0     _____-----
038 *      00         0xC6     __--___---
039 *      01         0x78     ____----_-
040 *      10         0xE1     _-____----
041 *      001        0x66     __--__--_-
042 *      010        0x96     __--_-__--
043 *      011        0x5C     ___---_-_-
044 *      100        0x99     _-__--__--
045 *      101        0x71     _-___---_-
046 *      110        0xC5     _-_-___---
047 *      0111       0x56     __--_-_-_-
048 *      1011       0x59     _-__--_-_-
049 *      1101       0x65     _-_-__--_-
050 *      1110       0x95     _-_-_-__--
051 *      11111      0x55     _-_-_-_-_-
052 *                          ^        ^
053 *                          start-   stop-
054 *                          bit      bit
055 *
056 * Limitation
057 * If we ever need to generate a pattern of four '1's followed by a '0' and
058 * land it on a the start of a byte boundary - Sorry - it can't be done !!
059 *
060 *
061 * makepckt.c
062 *
063 * Send an nmra packet out the serial port in such a way that the signal can
064 * just be amplified and put on the track.
065 *
066 * Copyright 1993 Kenneth Rice
067 *
068 * You may freely distribute this source code, and use all or part of
069 * this source code in all software including commercial, freeware,
070 * shareware and private applications.
071 *
072 * Please report bugs, fixes, etc to me at:
073 * kenr@xis.xerox.com
074 * or
075 * 73577,1653 (compuserve)
076 *
077 * Created 02/08/93
078 *   03/05/93 Works for all 3 byte packets. Still errors for 4 byte.
079 *   07/01/93 Renamed to makepckt.c to be nice to dos users.
080 *   10/23/93 Added backtracking and max length.
081 * </pre>
082 *
083 * @author Bob Jacobsen Copyright (C) 2001
084 *
085 */
086public class MakePacket {
087
088    private static int preambleLength = 15;
089    /* This should be a multiple of 5. */
090    private static final int BITSTREAM_BITS_PER_BYTE = 9;
091    /* number of bits per byte/
092     /* nmra   s01234567s (hex equiv - note that in signal, 0 bit is left) */
093    private static final int BITS_0 = 0xF0; /* 0      _____----- (0xF0) */
094
095    private static final int BITS_00 = 0xC6; /* 00     __--___--- (0xC6) */
096
097    private static final int BITS_01 = 0x78; /* 01     ____----_- (0x78) */
098
099    private static final int BITS_10 = 0xE1; /* 10     _-____---- (0xE1) */
100
101    private static final int BITS_001 = 0x66; /* 001    __--__--_- (0x66) */
102
103    private static final int BITS_010 = 0x96; /* 010    __--_-__-- (0x96) */
104
105    private static final int BITS_011 = 0x5C; /* 011    ___---_-_- (0x5C) */
106
107    private static final int BITS_100 = 0x99; /* 100    _-__--__-- (0x99) */
108
109    private static final int BITS_101 = 0x71; /* 101    _-___---_- (0x71) */
110
111    private static final int BITS_110 = 0xC5; /* 110    _-_-___--- (0xC5) */
112
113    private static final int BITS_0111 = 0x56; /* 0111   __--_-_-_- (0x56) */
114
115    private static final int BITS_1011 = 0x59; /* 1011   _-__--_-_- (0x59) */
116
117    private static final int BITS_1101 = 0x65; /* 1101   _-_-__--_- (0x65) */
118
119    private static final int BITS_1110 = 0x95; /* 1110   _-_-_-__-- (0x95) */
120
121    private static final int BITS_11111 = 0x55; /* 11111  _-_-_-_-_- (0x55) */
122
123
124    private static class Node {
125
126        int bitPattern;
127        int patternLength;
128    }
129    /* Node definition for first depth, prune largest tree. */
130
131    /**
132     * Set the Preamble Length - Default is 15 NRMA '1's Every NMRA
133     * packet decoded starts with a preamble Service mode requires longer
134     * preambles Thus this public function allowing user to define the lenght of
135     * desired preamble
136     *
137     * @param preambleLen int
138     * @return boolean true if preamble is a multiple of 5, otherwise fails and
139     *         returns false
140     */
141    public static boolean setPreambleLength(int preambleLen) {
142        //Just make sure that no negatives values are passed.
143        if (preambleLen <= 0) {
144            return (false);
145        }
146        // Check that preamble is a multiply of 5
147        if (preambleLen % 5 != 0) {
148            return (false);
149        }
150        preambleLength = preambleLen;
151        return (true);
152    }
153
154    /**
155     * Take in the packet as an array of Bytes and convert
156     * them into NMRA'1','0' representation, in preparation to be sent over a
157     * serial link.
158     *
159     * @param packet byte[] NRMA packet in a array of bytes
160     * @return int[]        first byte is length - 0 length indicates failed to do
161     */
162    public static int[] createStream(byte[] packet) {
163        int i = 0;
164        int mask = 0x80;
165        int[] bitStream = new int[(packet.length * BITSTREAM_BITS_PER_BYTE)
166                + preambleLength + 1];
167        int bitStreamIndex = 0;
168
169        /* Make into an array of ints for easier processing. */
170        /* do preamble */
171        for (bitStreamIndex = 0; bitStreamIndex < preambleLength; bitStreamIndex++) {
172            bitStream[bitStreamIndex] = 1;
173            /* Add Packet Start Bit - 0 */
174        }
175        bitStream[bitStreamIndex++] = 0;
176        /* Do packet bytes. */
177        for (i = 0; i < packet.length; i++) {
178            mask = 0x80;
179            while (mask > 0) {
180                bitStream[bitStreamIndex++] = (packet[i] & mask) != 0 ? 1 : 0;
181                mask = (mask >> 1);
182            }
183            /* Add byte seperator - 0 */
184            bitStream[bitStreamIndex++] = 0;
185        }
186        /* do end packet indicator */
187        bitStream[--bitStreamIndex] = 1;
188
189        /*
190         * So we now have a int array reflecting required packet byte structure
191         * => bitStream
192         * Now do the hard part - convert this into a serial stream
193         */
194        return (bitStreamToSerialBytes(bitStream));
195    }
196
197    /**
198     * Generate the serial bytes from the bit stream.
199     * <p>
200     * Basically this is a depth first, prune largest tree search, always going down the subtree
201     * that uses the most bits for the next byte. If we get an error, backtrack up
202     * the tree until we reach a Node that we have not completely traversed all the
203     * subtrees for and try going down the subtree that uses the second most bits.
204     * Keep going until we finish converting the packet or run out of things to try.
205     * <p>
206     * This is not guaranteed to find the shortest serial stream for a given
207     * packet, but it is guaranteed to find a stream if one exists. Also, it
208     * usually does come up with the shortest packet
209     * @param inputBitStream sequence of binary bits to send as DCC waveform
210     * @return sequence of long/short codes to send, coded as voltage high 1, 
211     * voltage low 0 values as aynch bytes to send at the DCC rate
212     */
213    static int[] bitStreamToSerialBytes(int[] inputBitStream) {
214        int currentBufferIndex;
215        int treeIndex = -1;
216        int serialStream[] = new int[inputBitStream.length];
217        Node tree[] = new Node[150];
218
219        for (currentBufferIndex = 0; currentBufferIndex < tree.length;
220                currentBufferIndex++) {
221            tree[currentBufferIndex] = new Node();
222            tree[currentBufferIndex].bitPattern = 0;
223            tree[currentBufferIndex].patternLength = 0;
224        }
225
226        /* Now generate the actual serial byte stream from the array of bits. */
227        currentBufferIndex = 0;
228        treeIndex = 1;
229        while (currentBufferIndex < inputBitStream.length) {
230            if (readFirstChild(inputBitStream, currentBufferIndex,
231                    inputBitStream.length - currentBufferIndex,
232                    tree[treeIndex])) {
233                /* Success, there is a Child at this level in the tree to read */
234                /* Move down the tree to next Node */
235                serialStream[treeIndex] = tree[treeIndex].bitPattern;
236                currentBufferIndex += tree[treeIndex++].patternLength;
237            } /* Allow outer loop control to take us down next level; */ else {
238                /* Need to add some code to cope with stradling '1's to stop
239                 backtrack from failure */
240                if (currentBufferIndex + 4 > inputBitStream.length) {
241                    serialStream[treeIndex] = BITS_11111;
242                    currentBufferIndex = inputBitStream.length;
243                } else {
244                    while (treeIndex > 0) {
245                        /* Inner loop to check all childs at this Node */
246                        /* If no more childs then need to bracktrack */
247                        treeIndex--;
248                        currentBufferIndex -= tree[treeIndex].patternLength;
249                        if (readNextChild(tree[treeIndex])) {
250                            serialStream[treeIndex] = tree[treeIndex].bitPattern;
251                            currentBufferIndex += tree[treeIndex++].patternLength;
252                            break;
253                        }
254                        if (treeIndex == 0) {
255                            serialStream[0] = 0;
256                            return (serialStream);
257                        }
258                    }
259                }
260            }
261        }
262        serialStream[0] = --treeIndex;
263        return (serialStream);
264    }
265
266    /**
267     * Find the next largest (ie longest length) child at this Node.
268     *
269     * @param thisNode (INPUT/OUTPUT) determine if there is another child
270     *                 if so update Node with ie the Bit
271     *                 pattern and its associated lenght
272     *
273     * @return false if one doesn't exist otherwise returns true
274     */
275    static boolean readNextChild(Node thisNode) {
276
277        switch (thisNode.bitPattern) {
278            /* Success - there is another child */
279
280            case BITS_00:
281            case BITS_01:
282                thisNode.bitPattern = BITS_0;
283                thisNode.patternLength = 1;
284                break;
285            case BITS_001:
286                thisNode.bitPattern = BITS_00;
287                thisNode.patternLength = 2;
288                break;
289            case BITS_010:
290            case BITS_011:
291                thisNode.bitPattern = BITS_01;
292                thisNode.patternLength = 2;
293                break;
294            case BITS_100:
295                thisNode.bitPattern = BITS_10;
296                thisNode.patternLength = 2;
297                break;
298            case BITS_0111:
299                thisNode.bitPattern = BITS_011;
300                thisNode.patternLength = 3;
301                break;
302            case BITS_1011:
303                thisNode.bitPattern = BITS_101;
304                thisNode.patternLength = 3;
305                break;
306            case BITS_1101:
307                thisNode.bitPattern = BITS_110;
308                thisNode.patternLength = 3;
309                break;
310            /* We have exhausted all children on this level */
311            default:
312                return false;
313        }
314        return (true);
315    }
316
317    /**
318     * Find the first largest (ie longest length) child
319     * at this Node.
320     *
321     * @param bs        (INPUT) Bit stream array
322     * @param offset    Offset in to buffer
323     * @param validBits (INPUT) number of valid bits in the bit stream
324     * @param thisNode  (OUTPUT) where to put largest child found ie the Bit
325     *                  pattern and its associated lenght
326     *
327     * @return false if one doesn't exist otherwise returns true
328     */
329    @SuppressWarnings("fallthrough")
330    static boolean readFirstChild(int bs[], int offset, int validBits,
331            Node thisNode) {
332        boolean b0 = false;
333        boolean b1 = false;
334        boolean b2 = false;
335        boolean b3 = false;
336        boolean b4 = false;
337        thisNode.patternLength = 0;
338
339        switch (validBits) { /* Note all cases fall through on purpose. */
340
341            default:
342                thisNode.patternLength = 5;
343                b0 = (bs[0 + offset] != 0);
344                b1 = (bs[1 + offset] != 0);
345                b2 = (bs[2 + offset] != 0);
346                b3 = (bs[3 + offset] != 0);
347                b4 = (bs[4 + offset] != 0);
348                if (b0 && b1 && b2 && b3 && b4) {
349                    thisNode.bitPattern = BITS_11111;
350                    break;
351                }
352            // fall through
353            case 4:
354                thisNode.patternLength = 4;
355                b0 = (bs[0 + offset] != 0);
356                b1 = (bs[1 + offset] != 0);
357                b2 = (bs[2 + offset] != 0);
358                b3 = (bs[3 + offset] != 0);
359                if (!b0 && b1 && b2 && b3) {
360                    thisNode.bitPattern = BITS_0111;
361                    break;
362                }
363                if (b0 && !b1 && b2 && b3) {
364                    thisNode.bitPattern = BITS_1011;
365                    break;
366                }
367                if (b0 && b1 && !b2 && b3) {
368                    thisNode.bitPattern = BITS_1101;
369                    break;
370                }
371                if (b0 && b1 && b2 && !b3) {
372                    thisNode.bitPattern = BITS_1110;
373                    break;
374                }
375            // fall through
376            case 3:
377                b0 = (bs[0 + offset] != 0);
378                b1 = (bs[1 + offset] != 0);
379                b2 = (bs[2 + offset] != 0);
380                thisNode.patternLength = 3;
381                if (!b0 && !b1 && b2) {
382                    thisNode.bitPattern = BITS_001;
383                    break;
384                }
385                if (!b0 && b1 && !b2) {
386                    thisNode.bitPattern = BITS_010;
387                    break;
388                }
389                if (!b0 && b1 && b2) {
390                    thisNode.bitPattern = BITS_011;
391                    break;
392                }
393                if (b0 && !b1 && !b2) {
394                    thisNode.bitPattern = BITS_100;
395                    break;
396                }
397                if (b0 && !b1 && b2) {
398                    thisNode.bitPattern = BITS_101;
399                    break;
400                }
401                if (b0 && b1 && !b2) {
402                    thisNode.bitPattern = BITS_110;
403                    break;
404                }
405            // fall through
406            case 2:
407                thisNode.patternLength = 2;
408                b0 = (bs[0 + offset] != 0);
409                b1 = (bs[1 + offset] != 0);
410                if (!b0 && !b1) {
411                    thisNode.bitPattern = BITS_00;
412                    break;
413                }
414                if (!b0 && b1) {
415                    thisNode.bitPattern = BITS_01;
416                    break;
417                }
418                if (b0 && !b1) {
419                    thisNode.bitPattern = BITS_10;
420                    break;
421                }
422            // fall through
423            case 1:
424                thisNode.patternLength = 1;
425                b0 = (bs[0 + offset] != 0);
426                if (!b0) {
427                    thisNode.bitPattern = BITS_0;
428                    break;
429                } else {
430                    thisNode.patternLength = 0;
431                }
432        }
433
434        return (thisNode.patternLength != 0);
435    }
436
437}