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.
Oct 26, 2015
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.
Setup VirtualBox
Update: upgrade virtualbox to latest version 5.0.6 and launch Ubuntu. Select "device->insert guest additions Image" to force insert VBoxGuestAdditions.iso, shutdown and reboot. Now I can switch to any windows resolution.
-----
My host is Windows 7 64bits. The guest OS is Ubuntu 14/ 64bits. I never thought it could have so many issues, so I wrote down what I did.
1. VirtualBox may not allow you to install 64bits Ubuntu. There was no 64bits OS in the drop down list. What I have to do is to enter into BIOS, enable "intel virtualization".
2. Once Ubuntu is installed, the first thing I did was right click on the desktop... what, there is no "launch terminal" session? Fortunately I remember the short cut is "Ctrl+Alt+T". The right button item for terminal definitely exist on my ubuntu 14/32bits and lower versions. Why people just removed it?
3. The screen resolution is bad. My screen is 1920*1080, while my guest gives me only 640*480, that makes it funny. What I have to do is to install a propriety driver, enable the driver $sudo apt-get install virtualbox-guest-dkms
and also run x window diagnose program $sudo xdiagnose to enable all 3 options
4. USB 2.0/3.0 was disabled by default, I have to install Oracle VM VirtualBox Extension Pack to enable USB EHCI/xHCI.
5. It is way to hard to adjust the disk size. I simply got errors
C:\Users\tiantan\VirtualBox VMs\ubuntu64>"C:\Program Files\Oracle\VirtualBox\VBo xManage.exe" modifyhd ubuntu64.vbox --resize 15000
VBoxManage.exe: error: Could not get the storage format of the medium 'C:\Users\ tiantan\VirtualBox VMs\ubuntu64\ubuntu64.vbox' (VERR_NOT_SUPPORTED)
VBoxManage.exe: error: Details: code VBOX_E_IPRT_ERROR (0x80bb0005), component M ediumWrap, interface IMedium, callee IUnknown
VBoxManage.exe: error: Context: "OpenMedium(Bstr(pszFilenameOrUuid).raw(), enmDe vType, enmAccessMode, fForceNewUuidOnOpen, pMedium.asOutParam())" at line 178 of file VBoxManageDisk.cpp
6. what means the "shared clipboard bidirectional"? It did never work on either way
7. the samba network sharing on my guest OS works some time, however not always. Hasn't figure out why. I have to install Filezilla FTP server on my Windows 7 as backup.Lame...
-----
My host is Windows 7 64bits. The guest OS is Ubuntu 14/ 64bits. I never thought it could have so many issues, so I wrote down what I did.
1. VirtualBox may not allow you to install 64bits Ubuntu. There was no 64bits OS in the drop down list. What I have to do is to enter into BIOS, enable "intel virtualization".
2. Once Ubuntu is installed, the first thing I did was right click on the desktop... what, there is no "launch terminal" session? Fortunately I remember the short cut is "Ctrl+Alt+T". The right button item for terminal definitely exist on my ubuntu 14/32bits and lower versions. Why people just removed it?
3. The screen resolution is bad. My screen is 1920*1080, while my guest gives me only 640*480, that makes it funny. What I have to do is to install a propriety driver, enable the driver $sudo apt-get install virtualbox-guest-dkms
and also run x window diagnose program $sudo xdiagnose to enable all 3 options
4. USB 2.0/3.0 was disabled by default, I have to install Oracle VM VirtualBox Extension Pack to enable USB EHCI/xHCI.
5. It is way to hard to adjust the disk size. I simply got errors
C:\Users\tiantan\VirtualBox VMs\ubuntu64>"C:\Program Files\Oracle\VirtualBox\VBo xManage.exe" modifyhd ubuntu64.vbox --resize 15000
VBoxManage.exe: error: Could not get the storage format of the medium 'C:\Users\ tiantan\VirtualBox VMs\ubuntu64\ubuntu64.vbox' (VERR_NOT_SUPPORTED)
VBoxManage.exe: error: Details: code VBOX_E_IPRT_ERROR (0x80bb0005), component M ediumWrap, interface IMedium, callee IUnknown
VBoxManage.exe: error: Context: "OpenMedium(Bstr(pszFilenameOrUuid).raw(), enmDe vType, enmAccessMode, fForceNewUuidOnOpen, pMedium.asOutParam())" at line 178 of file VBoxManageDisk.cpp
6. what means the "shared clipboard bidirectional"? It did never work on either way
7. the samba network sharing on my guest OS works some time, however not always. Hasn't figure out why. I have to install Filezilla FTP server on my Windows 7 as backup.Lame...
Subscribe to:
Posts (Atom)