How to reduce the code space for a hexadecimal ASCII chars conversion using a _small_ code space?

Question

How to reduce the code space for a hexadecimal ASCII chars conversion using a small code space?

In an embedded application, I have extraordinary limited space (note 1). I need to convert bytes, from serial I/O, with the ASCII values '0' to '9' and 'A' to 'F' to the usual hexadecimal values 0 to 15. Also, all the other 240 combinations, including 'a' to 'f', need to be detected (as an error).

Library functions such as scanf(), atoi(), strtol() are far too large to use.

Speed is not an issue. Code size is the the limiting factor.

My present method re-maps the 256 byte codes into 256 codes such that '0' to '9' and 'A' to 'Z' have the values 0 - 35. Any ideas on how to reduce or different approaches are appreciated.

unsigned char ch = GetData(); // Fetch 1 byte of incoming data;
if (!(--ch & 64)) {           // decrement, then if in the '0' to '9' area ...
  ch = (ch + 7) & (~64);      // move 0-9 next to A-Z codes
}
ch -= 54;                     // -= 'A' - 10 - 1
if (ch > 15) { 
  ; // handle error
}

---

Note 1: 256 instructions exist for code and constant data (1 byte data costs 1 instruction) in a PIC protected memory for a bootloader. This code costs ~10 instructions. Current ap needs a re-write & with only 1 spare instruction, reducing even 1 instruction is valuable. I'm going through it piece by piece. Also have looked at overall reconstruction.

Notes: PIC16. I prefer to code in 'C', but must do what ever it takes. Assembly code follows. A quick answer is not required.

if (!(--ch & 64)) { 
  002D:DECF   44,F   002E:BTFSC  44.6    002F:GOTO   034     
  ch = (ch + 7) & (~64); 
  0030:MOVLW  07     0031:ADDWF  44,W    0032:ANDLW  BF    0033:MOVWF  44
}// endif 
ch -= 54; 
  0034:MOVLW  36     0035:SUBWF  44,F

[edit best solution]
Optimizing existing solution as suggested by @GJ. In C, performing the ch += 7; ch &= (~64); instead of ch = (ch + 7) & (~64); saved 1 instruction. Going to assembly saved another by not having to reload ch within the if().

Rockrose

Answer 1

PIC16 family is RISC MCPU, so you can try to optimize your asm code. This is your c compilers asm code...

    decf    ch, f
    btfsc   ch, 6
    goto    Skip
    movlw   07
    addwf   ch, w
    andlw   0xBF
    movwf   ch
Skip    
    movlw   0x36
    subwf   ch, f

This is my optimization of upper code...

   decf     ch, w         //WREG = (--ch)
   btfsc    WREG, 6       //if (!(WREG & 64)) {
   goto     Skip  
   addlw    7             //WREG += 7
   andlw    0xBF          //WREG &= (~64)
Skip
   addlw    0x100 - 0x36  //WREG -= 54;
   movwf    ch            //ch = WREG
//
   addlw    0x100 - 0x10  //if (WREG > 15) { 
   btfsc    STATUS, 0     //Check carry
   goto     HandleError

...so only 7 opcodes (2 less) without range error check and 10 opcodes with range error check!

EDIT: Try also this PIC16 c compiler optimized function, not sure if works...

WREG = (--ch);                   
if (!(WREG & 64)) {              // decrement, then if in the '0' to '9' area ...
  WREG = (WREG + 7) & (~64);     // move 0-9 next to A-Z codes
}
ch = WREG - 54;                  // -= 'A' - 10 - 1 
if (WREG > 15) {    
  ; // handle error 
}

EDIT II: added version which is compatible with older PIC16 MCPUs not made in XLP technology, but code size is one opcode longer.

    decf    ch, f         ;//ch = (--ch)
    movf    ch, w         ;//WREG = ch
    btfsc   ch, 6         ;//if (!(ch & 64)) {
    goto    Skip  
    addlw   7             ;//WREG += 7
    andlw   0xBF          ;//WREG &= (~64)
Skip
    addlw   0x100 - 0x36  ;//WREG -= 54;
    movwf   ch            ;//ch = WREG
//    
    addlw   0x100 - 0x10  ;//if (WREG > 15) { 
    btfsc   STATUS, 0     ;//Check carry
    goto    HandleError

EDIT III: explanation

The 'D Kruegers' solution is also very good, but need some modification...

This code..

  if (((ch += 0xC6) & 0x80) || !((ch += 0xF9) & 0x80)) {
    ch += 0x0A;
  }

...we can translate to...

  if (((ch -= ('0' + 10)) < 0) || ((ch -= ('A' - '0' - 10)) >= 0)) {
    ch += 10; 
  }

After that we can optimize in asembler...

        call    GetData 
//if GetData return result in WREG then you do not need to store in  ch and read it again!
//      movwf   ch
//      movf    ch, w

        addlw   0x100 - '0' - 10     //if (((WREG -= ('0' + 10)) < 0) || ((WREG -= ('A' - '0' - 10)) >= 0)) {
        btfss   STATUS, 0   
        goto    DoAddx
        addlw   0x100 - ('A' - '0' - 10)
        btfsc   STATUS, 0       
    DoAddx
        addlw   10                   //WREG += 10; }
        movwf   ch                   //ch = WREG;       

        addlw   0x100 - 0x10         //if (WREG > 15) { 
        btfsc   STATUS, 0            //Check carry
        goto    HandleError

Branchiopod

Is btfsc WREG, 6 valid on a PIC16? – Mccaskill

@D Krueger: WREG is accessible only on newer PIC16 and PIC12 MCPUs marked as XLP technology. WREG is a copy of ALU working register at address 0x09. – Branchiopod

@Krueger: added also a version which is compatible with older PIC16 MCPUS. – Branchiopod

Thanks. In C, performing the ch += 7; ch &= (~64); instead of ch = (ch + 7) & (~64); saved 1 instruction. Going to assembly save another. – Rockrose

@chux: check also my EDIT III explanation :) – Branchiopod

Answer 2

With good compiler optimization, this may take less code space:

unsigned char ch = GetData(); // Fetch 1 byte of incoming data;

if (((ch += 0xC6) & 0x80) || !((ch += 0xF9) & 0x80)) {
  ch += 0x0A;
}

if (ch > 15) { 
  ; // handle error
}

Mccaskill

This code isn't OK! What should be the result if input is character @ (0x40)? – Branchiopod

@GJ.If on input ch == 0x40 then its final value will be 0xff, which will be caught by the (ch > 15) test. – Mccaskill

Thank-you. My best usage of your answer and variations was still +0 instruction over the original. (This has 3 branches versus original 2.) It took a while to understand your nifty approach, but it open up some thought. – Rockrose

Answer 3

Perhaps using ctype.h's isxdigit():

if( isxdigit( ch ) )
{
    ch -= (ch >= 'A') ? ('A' - 10) : '0' ;
}
else
{
    // handle error
}

Whether that is smaller or not will depend largely on the implementation of isxdigit and perhaps your compiler and processor architecture, but worth a try and far more readable. isxdigit() is normally a macro so there is no function call overhead.

An alternative is to perform the transformation unconditionally then check the range of the result:

ch -= (ch >= 'A') ? ('A' - 10) : 
                    (ch >= '0') ? '0' : 0 ;
if( ch > 0xf )
{
    // handle error
}

I suspect this latter will be smaller, but modification of ch on error may be unhelpful in some cases, such as error reporting the original value.

Sarmentum

Should that be ('A' - 10) rather than ('A' + 10) since you're subtracting that quantity from ch? – Lehrer

Thanks - Since isxdigit() returns true on a to f', ch takes on the values 42 to 47. I suppose an if() could be added. Assuming isxdigit() isn't some big lookup table, it likely uses 3 if()s. – Rockrose

@chux: I am not sure what you mean, the result in ch will be 0 to 15 as required. The transformation is performed if the digit is hexadecimal. Since isxdigit() is likely to be a macro you can find its complete definition in ctype.h. – Sarmentum

@chux: I have added an alternative that does not use isxdigit() but which modifies ch even if it is not a hex digit. – Sarmentum

isxdigit() returns true on 0-9, A-F and a-f. The 1st solution converts ch from 'A' into 10, good, but converts 'a' into 42 and is not detected passed to the // handle error. The second solution converts ':' to '?' into 10 to 15 and they are not detected in the // handle error. – Rockrose

My isxdigit() is indeed a macro: #define isxdigit(x) isamong(x,"0123456789ABCDEFabcdef"). Certainly longer than 10 instructions. BTW, later, I'll be in the wilderness for a few days. – Rockrose

@Sarmentum if ( ch < 0x0 .. can't never be true for an unsigned char – Septavalent

@chux: Your question clearly states '0' to '9' and 'A' to 'F'. I simply followed your spec. – Sarmentum

@jeb: true - even better. – Sarmentum

@chux: I am being thick I see what you mean about a to f. It needs an islower() test but the solution is increasingly unsatisfactory perhaps. One solution is to convert lower case to upper case before the transformation and accept lower case hex digits ch &= 0x20. – Sarmentum