My Stuff: 10/01/2014

Monday, October 13, 2014

Cheap ATMEL AVR ISP ICE from QinHeng

I bought this small USB stick from eBay. It supposedly can do JTAG and many other cool stuff for ATMEL microcontrollers.

Anyway, here is the detail how to use it:

The other end of the stick has dual-line 10-pin connector. The pins are:

Pin Purpose
------------------------------
1    TCK
2    GND
3    TDO
4    VTref
5    TMS
6    nSRT
7    VSupply
8    (nSRT)
9    TDI
10   GND

These pins are actually JTAG pins. The connections to the Microcontroller is as follow (the pullup resistors are all 4.7k):

The USB id:

$ lsusb
...
Bus 003 Device 006: ID 1a86:7523 QinHeng Electronics HL-340 USB-Serial adapter
...

Upon inserting the stick to my PC's USB (running Ubuntu Linux):

[118845.955500] ch341-uart ttyUSB0: ch341-uart converter now disconnected from ttyUSB0
[118845.955541] ch341 3-2:1.0: device disconnected
[118851.692044] usb 3-2: new full-speed USB device number 6 using ohci-pci
[118851.901261] usb 3-2: New USB device found, idVendor=1a86, idProduct=7523
[118851.901271] usb 3-2: New USB device strings: Mfr=0, Product=2, SerialNumber=0
[118851.901276] usb 3-2: Product: USB2.0-Serial
[118851.904683] ch341 3-2:1.0: ch341-uart converter detected
[118851.940428] usb 3-2: ch341-uart converter now attached to ttyUSB0

To use it as programmer, we can use avrdude:

$ sudo avrdude -c avrisp -P /dev/ttyUSB0 -pm328p <other options>

To debug, we can use another opensource, AvaRICE (from ubuntu, just do "apt-get install avarice").

For example (this is just to show how to use it, as my ICE stick is not connected to any target device yet so it reports it "No configuration available for device ID: ffff"):

$ sudo avarice --jtag /dev/ttyUSB0 -1
AVaRICE version 2.11, Jan 17 2014 02:53:19

Defaulting JTAG bitrate to 250 kHz.

JTAG config starting.
Hardware Version: 0xc3
Software Version: 0x80
Reported JTAG device ID: 0xFFFF
No configuration available for device ID: ffff

The avarice can be set as a gdb server mode, so we can debug the target removely. For example, to make it as gdb-server listening on port 4242.

$ sudo avarice --jtag /dev/ttyUSB0 :4242

From another PC (or the same PC, if host and server is on the same machine), we open gdb, and connect:

$ gdb
GNU gdb (Ubuntu 7.7-0ubuntu3.1) 7.7
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "i686-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word".
(gdb) target remote 127.0.0.1:4242

Using PicKit2 Programmer to program Atmel's microcontrollers

Many hobbists are familiar with Arduino kit. This beast uses various Microcontrollers from Atmel. For example, Arduino UNO uses AtMega 328p.

Normally, we use the pcb kit to program the chip, as the Arduino (or the clones) use USB to serial chip to translate USB to serial needed to program Arduino.

For people who has done hacking on PIC microcontrollers from MicroChip and wants to use bare-metal chip, they can program the Atmel chips using the existing cheap PicKit2 programmer. What they need just the Pickit2 programmer and a software tool called avrdude.

The pin connections:

AVR   - PICKit2 (pin):

-----------------------

RST   - VPP/MCLR (1)
VDD   - VDD Target (2) -- optional if AVR self powered
GND   - GND (3)
MISO  - PGD (4)
SCLK  - PDC (5)
MOSI  - AUX (6)

Some of command examples are shown below:

To write our firmware to the flash in AtMega 328p:

$ avrdude -c pickit2 -p m328p -v -V -U flash:w:"myfirmware.hex":a

To upload bootloader (e.g. to upload ARDUINO bootloader):

$ avrdude -c pickit2 -p m328p -v -V -U boot:w:"boot.hex":a

Left shift by negative number used to test unique characters in a string

What is the outcome of this?

val=-32;
mask = 1<<val;

I tried to execute it on Python, it failed with error message.

But if I do it in C or C++, I get something else. Turn out, this depends o the compiler and CPU we use. As I use Pentium4 and GCC to compile this, the following snippet of the generated assembly language is interesting:

.L4:
movsbl (%edx), %ecx
movl %esi, %edi
addl $1, %edx
subl $97, %ecx
sall %cl, %edi
testl %eax, %edi
jg .L5
orl %edi, %eax

.L2:

What is "sall" above? It is Intel CPU's mnemonic for "Shift Arithmetic Left for Long Integer".

In the machine code, -32 is transformed to Second-complement of 32:

32 = 0b00100000

~32 = 0b11011111

~32+1 = 0b11100000 = -32

According Wikipedia, arithmetic shift left maintains the MSBit, so in this case MSB is always 1. Also, Intel CPUs only shifts the first 5-bits of the shifting bits (in this case, 5-bit LSB of 0b11100000 which is 0), so 1<<-32 is actuall 1<<0 = 1.

What about 1<<-33?

33 = 0b00100001

~33 = 0b11011110

~32+1 = 0b11100001 = -33

The first five bits is 1, so 1<<-33 = 1<<1 = 2

What about 1<<-31?

31 = 0b00011111

~31 = 0b11100000

~31+1 = 0b11100001 = -31

The first five bits is 1, so 1<<-31 = 1<<1 = 0x00000010

What about 1<<-7?

7 = 0b00000111

~7 = 0b11111000

~7+1 = 0b11111001 = -7

The first five bits is 1, so 1<<-7 = 1<<25 = 0x02000000

Now, how do we use this to check a uniqueness of characters in a string?

Alphabet 'A' to 'Z' has 26 characters. Alphabet 'a' to 'z' has also 26 characters.

The difference between the character i in a string is: str[i] - 'a'. Now this is the interesting part: if we declare a 32-bit variable (which is enough to cover 'A' to 'Z') where each bit corresponds to the occurence of each character in alphabet, we can determine if the character has been used before and tell the string has unique characters or not (e.g, bit 1 to tell if character 'A' has been used or not, etc.)

'A' - 'a' = -32

...

'Z' - 'a' = -7

...

'a' - 'a' = 0

...

'Z' - 'a' = 25

if we shift 1 to -32, it is the same as 1<<0. If we shift 1 to -33 it is the same as 1<<1, so on.

1<<-32 = 0x01

1<<-31 = 0x02

...

1<<-7 = 1<<25 = 0x2000000

1<<0 = 0x01

1<<1 = 0x02

...

1<<25 = 0x2000000

so:

1<<('A'-'a') == 1<<('a'-'a') = 0x01

1<<('B'-'a') == 1<<('b'-'a') = 0x02

...

1<<('Z'-'a') == 1<<('z'-'a') = 0x2000000

So the code is:

for (i=0; i<strlen(s); i++)

{

val = s[i] - 'a';

if (flags & (1 << val))

return 0; /* the string is not unique */

flags |= 1 << val;

}
return 1;

Notice this algorithm might not work on different machine with different compiler (as shifting by negative number is undefined in standard C).

The Use of c++decl

cdecl and c++decl are two nice tools to check syntax or to generate declaration of C and C++ respectively.

for example, using c++decl (the text in bold is the one we type):

$ cdecl

Type `help' or `?' for help
c++decl>

c++decl> declare foo as pointer to member of class X function (arg1, arg2) returning reference to class Y

class Y &(X::*foo)(arg1, arg2)

c++decl>

c++decl> declare foo as reference to class X

class X &foo

c++decl>

c++decl> cast foo into reference to class X

(class X &)foo

c++decl>

We can also use them to check a declaration syntax, for example:

c++decl> explain int (*a)[5]

declare a as pointer to array 5 of int

c++decl>

c++decl> explain long **foo[10]

declare foo as array 10 of pointer to pointer to long

c++decl>

c++decl> explain int*&(foo);

declare foo as reference to pointer to int

c++decl>

The function can also be used to translate an english declaration to C (or C++) declaration. For example:

$ c++decl declare "i as array 5 of pointer to function(int,int) returning reference to class X"

class X &(*i[5])(int , int )

$

$ c++decl declare "i as array 5 of pointer to function(reference to class X,constant reference to int) returning reference to class X"

class X &(*i[5])(class X &, int & const )

$

$ c++decl declare "const_ptr as const pointer to const int"

const int * const const_ptr

$ c++decl declare "const_ptr as const pointer to const reference to class X"

class X & const * const const_ptr

c++decl> declare myfunc as const pointer to function (const pointer to int, reference to class X) returning void

void (* const myfunc)(int * const , class X &)

c++decl>

c++decl> declare myfunctpr as array of pointer to function (void) returning int

int (*myfunctpr[])(void )

c++decl>

declare myptr as pointer to array 10 of struct MyStruct

struct MyStruct (*myptr)[10]

c++decl>

Saturday, October 4, 2014

Odd Numbers with Parity

#!/usr/bin/python

table=[]
for n in range(0,256):
    p=False
    while n:
        p = not p
        n &= n-1
    table.append(p)

parity_odd = []

print "Odd numbers with Parity:"



for i in range(0,256):
    if (i%2) and (table[i]):
        parity_odd.append(i)
        print i,

Result:

Odd numbers with Parity:
1 7 11 13 19 21 25 31 35 37 41 47 49 55 59 61 67 69 73 79 81 87 91 93 97 103 107 109 115 117 121 127 131 133 137 143 145 151 155 157 161 167 171 173 179 181 185 191 193 199 203 205 211 213 217 223 227 229 233 239 241 247 251 253

Thursday, October 2, 2014

Fastest Fibonacci Sequencer

This algorithm is based on Fast-doubling as explained in Fast Fibonacci algorithms.

Given F(k) and F(k+1), we can calculate these equations:

F(2k) = F(k)[2F(k+1)−F(k)]
F(2k+1) = F(k+1)2+F(k)2.

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

#ifdef DEBUG
#define DBGMSG(x)       printf x 
#else
#define DBGMSG(x)
#endif

typedef unsigned long long num_type;

void _fib(int n, num_type *fn, num_type *fn_1);

num_type fibonacci(uint n, num_type *s)
{
 int i;
    num_type fn=0, fn_1=1;

 if (!s)
  return 0;

 if (n < 2)
    {
  return 1;
    }
    for(i=1; i<n; i++)
    {
        _fib(i, &fn, &fn_1);
        DBGMSG(("i=%u, n=%u, fn=%llu, fn+1=%llu\n", i, n, fn, fn_1));
        s[i] = fn;
    }
    return s[n];
}

/*
 * This is base on matrix exponentiation algorithm:
 * where:
 *  f(2k) = f(k)*{ 2*f(k+1) - f(k)}         ---> c
 *  f(2k+1) = f(k)^2 + f(k+1)^2             ---> s
 *
 *  if we plugin k = n/2, we get f(n) and f(n+1)
 */
void _fib(int n, num_type *fn, num_type *fn_1)
{
    num_type c,d;
    num_type a, b;

    DBGMSG( ("%s: Initially n=%u, fn=%llu, fn_1=%llu\n", __FUNCTION__, n, *fn, *fn_1) );
    if (n==0)
    {
        *fn = 0;        // fn
        *fn_1 = 1;      // fn+1
        return; 
    }
    else {
        a = *fn;
        b = *fn_1;
    }
    _fib(n>>1, &a, &b);
    DBGMSG (("%s: local fn=%llu, fn_1=%llu\n", __FUNCTION__, a, b));
    c = a * (2*b - a);
    d = b*b + a*a;
    DBGMSG( ("%s: c=%llu, d=%llu\n", __FUNCTION__, c, d) );
    if (n % 2 == 0)
    {
        // n is even
        *fn = c;
        *fn_1 = d;
    }
    else {
        *fn = d;
        *fn_1 = c+d;
    }
}

int main(int argc, char *argv[])
{
 uint n;
 uint f;
 int i;
 num_type *result;
    char *sbuf;
    int status = 0;

    if (argc > 1)
        n = atoi(argv[1]);
    else {
     printf("Enter a number: ");
        sbuf = (char *)malloc(50);
     status = (getline(&sbuf, &n, stdin) > 0);
        if (status == 0) {
      n = atoi(sbuf);
            free(sbuf);
        }
       else {
            printf("Error in input\n");
            return (1);
        }
    }
    if (n <= 0)
    {
        printf("What have yo done???\n");
        return(0);
    }
    if (status == 0)
 {
     result = (num_type *)malloc(n*sizeof(unsigned long long));
     f = fibonacci(n, result);
  printf("Fibonacci sequence: ");
  for(i=0; i<n; i++)
   printf("%llu ", result[i]);
  printf("\n");
        if (result)
      free(result);
    }
}