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}