Finally I am working on armv8 soc now. At the very beginning I need a mutex, which is essential for multiple core processors. The old strex/lderx on longer available, now we have ldxr/stxr instead
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.dht0008a/ch01s03s02.html
get_lock PROC
mov w1, #0x1
try_loop
ldaxr w2, [x0]
cbnz w2, try_loop
stxr w2, w1, [x0]
cbnz w2, try_loop
ret
ENDP
free_lock PROC
mov w1, #0x0
stlr w1, [x0]
ret
ENDP
try_lock PROC
mov w1, #0x1
ldaxr w2, [x0]
cbnz w2, exit
stxr w2, w1, [x0]
exit
mov w0, w2
ret
ENDP
Jan 29, 2016
Jan 28, 2016
C++ string::split
I can understand the reason why C does not provide the string split function, but C++ is another story. A guy told me today C++ is going to add an split function, but not in C++11. It is been so late. I always have to write something like this
that's too much job from Java's split, no mention the powerful regex based split in Perl.
#include <sstream>
#include <vector>
std::vector<std::string> split(const std::string& s, const char delim){
std::vector<std::string> res;
std::string item;
std:stringstream ss(s);
while(std::getline(ss, item, delim)) {
if(!item.empty()) res.push_back(item);
}
return res;
}
that's too much job from Java's split, no mention the powerful regex based split in Perl.
Assembly conditional compile for armcc
I have a bare metal code based which runs good on ARM Cortex-A7. Now I want run the same code on ARM Cortex-R5 without major change of the code, and keep the 2 projects share the same code base by compiling options. It is easy to identify the target by defining pre-processor marcos in make file and use #ifdef for C language.
It has the similar thing for armcc. Just define flags for ARM assembler like this
--predefine "CORTEX5 SETA 1"
This option defines a marco CORTEXR5, and assign value 1 to it, In the assembly I can easily use (make sure you have tab before IF/ELSE/ENDIF)
IF CORTEXR5 == 1
nop
ELSE ;Cortex-A7
smc #0
ENDIF
An alternative way is to define the marco in assembly source file
GBLA CORTEXR5
CORTEXR5 SETA 1
I prefer the previous one since it is easier to manage thru makefile or DS-5's build configuration.
It has the similar thing for armcc. Just define flags for ARM assembler like this
--predefine "CORTEX5 SETA 1"
This option defines a marco CORTEXR5, and assign value 1 to it, In the assembly I can easily use (make sure you have tab before IF/ELSE/ENDIF)
IF CORTEXR5 == 1
nop
ELSE ;Cortex-A7
smc #0
ENDIF
An alternative way is to define the marco in assembly source file
GBLA CORTEXR5
CORTEXR5 SETA 1
I prefer the previous one since it is easier to manage thru makefile or DS-5's build configuration.
Dec 7, 2015
DS-5 script disable memory verification
It is not a surprise some bits of a registers of a SOC are read-only. That means you can not change the value of the bits, thus a writing operation won't change the value. However, DStream always check the value and thus make it annoying to do batch update of registers. Here is on way to disabled it in DS-5 script
stop
wait 1s
show architecture
show version
info core
memory 0x00000000A0000000 +0x30000000 nocache noverify nobp nohbp
memory set 0x00000000A0014008 32 0x00404500
memory set 0x00000000A0002000 32 0x00010000
stop
wait 1s
show architecture
show version
info core
memory 0x00000000A0000000 +0x30000000 nocache noverify nobp nohbp
memory set 0x00000000A0014008 32 0x00404500
memory set 0x00000000A0002000 32 0x00010000
Oct 26, 2015
Upgraded to DS-5 5.22
Finally I upgraded to DS-5 5.22 since I need the ARM v8 support. There are 2 pitfalls during the upgrade.
1. Eclipse asked me to upgrade my DS-5's firmware. Well, embarrassingly, the FW upgrade utility can not find ANY DS-box in my network. There was at least 3 boxes in the same ethernet segment though. I have to hooked up the USB cable to download the firmware.
2. To connect to the board, there is no longer need to detect and save the board configuration file then import it with "cdbimport". Now you may just type "platform configuration" in the "Quick Access" box in eclipse and you will be able to identify the chip from DS-5. Supper cool, this function should be included earlier.
I also installed 5.22 on a Ubuntu14/64bits machine. The installation was smooth, the installation just missed to create desktop shortcut for me, but I can run /opt/local/bin/DS5-5-22/bin/eclipse directly.
1. Eclipse asked me to upgrade my DS-5's firmware. Well, embarrassingly, the FW upgrade utility can not find ANY DS-box in my network. There was at least 3 boxes in the same ethernet segment though. I have to hooked up the USB cable to download the firmware.
2. To connect to the board, there is no longer need to detect and save the board configuration file then import it with "cdbimport". Now you may just type "platform configuration" in the "Quick Access" box in eclipse and you will be able to identify the chip from DS-5. Supper cool, this function should be included earlier.
I also installed 5.22 on a Ubuntu14/64bits machine. The installation was smooth, the installation just missed to create desktop shortcut for me, but I can run /opt/local/bin/DS5-5-22/bin/eclipse directly.
Oct 23, 2015
(-1)^(1/3)
Q: calculate (-1)^(1/3), here ^ is power operation. You are given normal mathematical functions: + - * / log exp cos sin
x^y = exp( log(x^y)) = exp( y * log(x))
x is negative, we need to know log(-1)
log(-1) = log( i^2) = 2 log(i)
let's assume
log( i) = i*a
i = exp (log(i)) = exp (i*a) = cos(a) + i*sin(a)
sin(a) = 1, cos(a) = 0
a = 2*k*pi + pi/2
log(-1) = 2log(i) = 2*i*a = (pi + 4*k*pi)*i
x^y = exp( 1/3 * log(-1))
The possible answers:
k=0, x^y = exp( 1/3 * pi * i) = cos(pi/3) + i*sin(pi/3)
k=1, x^y = exp( (pi + 4*pi)*i/3) = cos( 5*pi/3) + i * sin( 5*pi/3)
k=2, x^y = exp( 9*pi*i/3) = cos(pi) + i*sin(pi) = -1
----- I should be much more simple -----
x=-1, x=e^(i*pi)=e^(i*3*pi)=e^(i*5*pi)
answer is
x^(1/3) = e^(i*1/3*pi), e^(i*5/3*pi), e^(i*pi)
Interesting thing is, Matlab will only list one answer.
x^y = exp( log(x^y)) = exp( y * log(x))
x is negative, we need to know log(-1)
log(-1) = log( i^2) = 2 log(i)
let's assume
log( i) = i*a
i = exp (log(i)) = exp (i*a) = cos(a) + i*sin(a)
sin(a) = 1, cos(a) = 0
a = 2*k*pi + pi/2
log(-1) = 2log(i) = 2*i*a = (pi + 4*k*pi)*i
x^y = exp( 1/3 * log(-1))
The possible answers:
k=0, x^y = exp( 1/3 * pi * i) = cos(pi/3) + i*sin(pi/3)
k=1, x^y = exp( (pi + 4*pi)*i/3) = cos( 5*pi/3) + i * sin( 5*pi/3)
k=2, x^y = exp( 9*pi*i/3) = cos(pi) + i*sin(pi) = -1
----- I should be much more simple -----
x=-1, x=e^(i*pi)=e^(i*3*pi)=e^(i*5*pi)
answer is
x^(1/3) = e^(i*1/3*pi), e^(i*5/3*pi), e^(i*pi)
Interesting thing is, Matlab will only list one answer.
Oct 15, 2015
A Notes to Hacker's Delight
Hacker's delight is a interesting book. The only problem is it skiped many steps and hard to follow. For example, one of the topic is how to cout the number of binary 1s for a unsigned interger?
1. Easy answer start from here
unsigned int CountBitOne(unsigned int value)
{
unsigned int count = 0;
while(value)
{
count += value & 1;
value >>= 1;
}
return count;
}
Note: don't use for loop! That's not efficient as while loop. Think about the sparse 1 case.
2. A well know trick.
unsigned int CountBitOne(unsigned int x)
{
unsigned int count = 0;
while(x)
{
++count;
x &= (x -1);
}
return count;
}
It is easy to prove x&(x-1) reset the least significiant bit of 1 of value. Suppose we have 8bits interger value
x b'XXXX1000 (Capital X means either 1 or 0)
x-1 b'XXXX0111
x&(x-1) b'XXXX0000
3. Can you do more optimization? Look up table is a good, and probbaly the fast solution, just make sure your lookup table is always in cache.
4. Method 1 and 2 count one bit at one time. Can we do more bits at the same time?
Divide and Conquer Algorithm. Suppose there is a 8bit integer 213(11010101 in binary), the algorithm works like this(each time merge two neighbor blocks):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
uint32_t CountBitOne(uint32_t x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
I changed the parameter's type to uint32_t since the introduction of magic binary numbers.
5. Divide and conqure method provided in Hacker's delight
https://books.google.com/books?id=iBNKMspIlqEC&pg=PA66&hl=en#v=onepage&q&f=false
uint32_t pop(uint32_t x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
The first line of this algorith has the same effect as method 4, proved by truth table
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
6. Last one is the so called "fastest way—without using lookup tables and popcount.", copied from
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
It counts the set bits with just 12 operations.
uint32_t popcount(uint32_t v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
The trick is to multiply the result by 0b10101010 which has an interesting property. If our number has four bytes, A B C D, it will result in a new number with these bytes A+B+C+D B+C+D C+D D. A 4 byte number can have maximum of 32 bits set, which can be represented as 0b00100000.
All we need now is the first byte which has the sum of all set bits in all the bytes, and we get it by >> 24.
7. Intel x86 CPU has a POPCOUNT in SSE instruction set to count the number of 1s. On the GNU compiler you can just use:
int __builtin_popcount (unsigned int x);
In the worst case the compiler will generate a call to a function. In the best case the compiler will emit a cpu instruction to do the same job faster. Unfortunately there is no equivelant on ARM yet.
8. Why I have to count 2 bits by 2 bits? A very interesting method has been developed at the MIT in the 1970's:
int bitcount(unsigned int n)
{
register unsigned int tmp;
tmp = n - ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
MIT HAKMEM Count is funky. Consider a 3 bit number as being 4a+2b+c. If we shift it right 1 bit, we have 2a+b. Subtracting this from the original gives 2a+b+c. If we right-shift the original 3-bit number by two bits, we get a, and so with another subtraction we have a+b+c, which is the number of bits in the original number. How is this insight employed? The first assignment statement in the routine computes tmp. Consider the octal representation of tmp. Each digit in the octal representation is simply the number of 1's in the corresponding three bit positions in n. The last return statement sums these octal digits to produce the final answer. The key idea is to add adjacent pairs of octal digits together and then compute the remainder modulus 63. This is accomplished by right-shifting tmp by three bits, adding it to tmp itself and ANDing with a suitable mask. This yields a number in which groups of six adjacent bits (starting from the LSB) contain the number of 1's among those six positions in n. This number modulo 63 yields the final answer. For 64-bit numbers, we would have to add triples of octal digits and use modulus 1023. This is HACKMEM 169, as used in X11 sources. Source: MIT AI Lab memo, late 1970's.
1. Easy answer start from here
unsigned int CountBitOne(unsigned int value)
{
unsigned int count = 0;
while(value)
{
count += value & 1;
value >>= 1;
}
return count;
}
Note: don't use for loop! That's not efficient as while loop. Think about the sparse 1 case.
2. A well know trick.
unsigned int CountBitOne(unsigned int x)
{
unsigned int count = 0;
while(x)
{
++count;
x &= (x -1);
}
return count;
}
It is easy to prove x&(x-1) reset the least significiant bit of 1 of value. Suppose we have 8bits interger value
x b'XXXX1000 (Capital X means either 1 or 0)
x-1 b'XXXX0111
x&(x-1) b'XXXX0000
3. Can you do more optimization? Look up table is a good, and probbaly the fast solution, just make sure your lookup table is always in cache.
4. Method 1 and 2 count one bit at one time. Can we do more bits at the same time?
Divide and Conquer Algorithm. Suppose there is a 8bit integer 213(11010101 in binary), the algorithm works like this(each time merge two neighbor blocks):
+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | <- x
| 1 0 | 0 1 | 0 1 | 0 1 | <- first time merge
| 0 0 1 1 | 0 0 1 0 | <- second time merge
| 0 0 0 0 0 1 0 1 | <- third time ( answer = 00000101 = 5)
+-------------------------------+
uint32_t CountBitOne(uint32_t x)
{
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
return x;
}
I changed the parameter's type to uint32_t since the introduction of magic binary numbers.
5. Divide and conqure method provided in Hacker's delight
https://books.google.com/books?id=iBNKMspIlqEC&pg=PA66&hl=en#v=onepage&q&f=false
uint32_t pop(uint32_t x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
The first line of this algorith has the same effect as method 4, proved by truth table
---------------------------------------------
| v | (v >> 1) & 0b0101 | v - x |
---------------------------------------------
0b00 0b00 0b00
0b01 0b00 0b01
0b10 0b01 0b01
0b11 0b01 0b10
6. Last one is the so called "fastest way—without using lookup tables and popcount.", copied from
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
It counts the set bits with just 12 operations.
uint32_t popcount(uint32_t v) {
v = v - ((v >> 1) & 0x55555555); // put count of each 2 bits into those 2 bits
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits
return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
The trick is to multiply the result by 0b10101010 which has an interesting property. If our number has four bytes, A B C D, it will result in a new number with these bytes A+B+C+D B+C+D C+D D. A 4 byte number can have maximum of 32 bits set, which can be represented as 0b00100000.
All we need now is the first byte which has the sum of all set bits in all the bytes, and we get it by >> 24.
7. Intel x86 CPU has a POPCOUNT in SSE instruction set to count the number of 1s. On the GNU compiler you can just use:
int __builtin_popcount (unsigned int x);
In the worst case the compiler will generate a call to a function. In the best case the compiler will emit a cpu instruction to do the same job faster. Unfortunately there is no equivelant on ARM yet.
8. Why I have to count 2 bits by 2 bits? A very interesting method has been developed at the MIT in the 1970's:
int bitcount(unsigned int n)
{
register unsigned int tmp;
tmp = n - ((n >> 1) & 033333333333)
- ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
MIT HAKMEM Count is funky. Consider a 3 bit number as being 4a+2b+c. If we shift it right 1 bit, we have 2a+b. Subtracting this from the original gives 2a+b+c. If we right-shift the original 3-bit number by two bits, we get a, and so with another subtraction we have a+b+c, which is the number of bits in the original number. How is this insight employed? The first assignment statement in the routine computes tmp. Consider the octal representation of tmp. Each digit in the octal representation is simply the number of 1's in the corresponding three bit positions in n. The last return statement sums these octal digits to produce the final answer. The key idea is to add adjacent pairs of octal digits together and then compute the remainder modulus 63. This is accomplished by right-shifting tmp by three bits, adding it to tmp itself and ANDing with a suitable mask. This yields a number in which groups of six adjacent bits (starting from the LSB) contain the number of 1's among those six positions in n. This number modulo 63 yields the final answer. For 64-bit numbers, we would have to add triples of octal digits and use modulus 1023. This is HACKMEM 169, as used in X11 sources. Source: MIT AI Lab memo, late 1970's.
Subscribe to:
Posts (Atom)