I find google notebook is a convenient tool. You can take note quite freely during surfing. And you can share your notebook quite easy too. I think it is even easier than Blog. Some of my exported notebook:
Programming
Smart phone
Monday, November 24, 2008
Friday, July 18, 2008
An algorithm to render PDF on small devices
I am interested in ebook reader for quite a while. But after trying with a 6-inch e-ink reader (Hanlin V3), I found it is almost useless to read normal PDF files (A4 size) on these devices. The font size is too small, while the page size is too wide. So, a method to render PDF for these small devices is thought about and prototyped. The details are as follow:
- Convert pdf to image. I use pdftoppm of xpdf. Such as: pdftoppm -r 180 -f 245 -l 245 -gray -aa yes a.pdf a
- Analyze the generated images. Break page into lines.
- Divide each line long enough to two segments.
- Rearrange the segments into a new page, with half of the width.
No state updating: functional language
The programming model of command language is state machine. Such as in C, every variable is a state, one of the most common statements are assigning new value to a variable, that is, state updating. But in functional programming language, there is no state updating, how to program without state updating? Let's begin with a simple example of bank account management system.
In erlang, a functional programming language:
Notes:
struct account
{
char *name;
int remain;
struct account *next;
};
#define OP_NOP 0
#define OP_WITHDRAW 1
#define OP_DEPOSIT 2
#define OP_PRINT 3
#define OP_EXIT 4
void deposit(struct account *account, int val)
{
account->remain += val;
}
void withdraw(struct account *account, int val)
{
account->remain -= val;
}
int main(int argc, char *argv[])
{
struct account *accounts = NULL;
char *name;
int op = OP_NOP, val;
while (op != OP_EXIT) {
op = read_operation();
case OP_WITHDRAW:
case OP_DEPOSIT:
name = read_name();
account = list_find(accounts, name);
val = read_val();
if (op == OP_WITHDRAW)
withdraw(account, val);
else
deposit(account, val);
break;
case OP_NEW:
name = read_name();
account = malloc(sizeof(struct account));
account->name = name;
account->remain = 0;
list_add(&accounts, account);
break;
case OP_PRINT:
/* a macro to iterate every element of list */
list_for_each(accounts, account) {
printf("Name: %s\tRemain: %d\n", account->name, account->remain);
}
break;
case OP_EXIT:
break;
}
}
return 0;
}
In erlang, a functional programming language:
-module(bank).
-export([service/1]).
deposit(Account, Val) ->
{Name, Remain} = Account,
{Name, Remain + Val}.
withdraw(Account, Val) ->
{Name, Remain} = Account,
{Name, Remain - Val}.
print_account({Name, Remain}) ->
io:format("Name: ~s Remain: ~B~n", [Name, Remain]).
service(Accounts) ->
{ok, [Operation|_]} = io:fread("Operation: ", "~a"),
if
Operation == deposit; Operation == withdraw ->
{ok, [Name|_]} = io:fread("Name: ", "~s"),
{ok, [Val|_]} = io:fread("Val: ", "~d"),
case lists:keysearch(Name, 1, Accounts) of
false ->
io:format("Error: no such account.~n"),
NewAccounts = Accounts;
{value, Account} ->
case Operation of
deposit ->
NewAccount = deposit(Account, Val);
withdraw ->
NewAccount = withdraw(Account, Val)
end,
NewAccounts = lists:keyreplace(Name, 1, Accounts,
NewAccount)
end,
service(NewAccounts);
Operation == new ->
{ok, [Name|_]} = io:fread("Name: ", "~s"),
case lists:keymember(Name, 1, Accounts) of
true ->
NewAccounts = Accounts,
io:format("Error: account already exist.~n");
false ->
NewAccounts = [{Name, 0} | Accounts]
end,
service(NewAccounts);
Operation == print ->
lists:foreach(fun print_account/1, Accounts),
service(Accounts);
Operation == exit ->
ok;
true ->
io:format("Error: unknown operation~n"),
service(Accounts)
end.
Notes:
- In functional programming language, instead of updating object (value) in-place, every time a new object (value) is constructed. In example above, in C, deposit() change account->remain directly, while in erlang, a new account is constructed and returned.
- If data of program is organized in a hierarchical way, to change the data in leaf, in command language, only the leaf is changed in place; in functional language, all data structure from that leaf to root will be reconstructed. In example above, in C, during deposit operation, only the corresponding account object is changed in-place, while in erlang, both corresponding account object and the whole account list will be re-constructed. With the help of carefully designed implementation, althought the performance of that in functional language is wrose, it is not so bad as it appears.
- In functional programming language, instead of updating the binding of variable name to new value directly, a new scope is constructed and in the new scope, same variable name is binded to a new value. In example above, during "new" operation, accounts may be bind to a new value, in erlang, a new scope is constructed by "recursing", that is, the new constructed account list is bind to Accounts in a new scope. Thanks to the "tail recursing" optimization, the performance is not so bad.
- How to shared objects in functional programming language? Such as in a database system, the cached database table should be shared between service threads.
Saturday, April 28, 2007
OS as parallel system
- There are subsystems as following in Linux kernel
- process management (virtual memory system, kernel entry point)
- physical memory management system
- file system
- device driver, device management
- network system
- The subsystems in Linux kernel like the "server" in micro-kernel operating system. They can be seen as multi-thread server too. Although the Linux kernel provides multi-process environment for user space, the kernel itself should be seen as a multi-thread program, because everything is shared.
- Most resources are not shared between processes in process management system, i.e., the virtual memory system is not shared between processes, while they are shared between threads.
- Process/thread is used as one of the parallel roles, the other parallel roles include IRQ handler, softirq, tasklet, work queue, timer operations. The subsystems in Linux kernel can be seen as multi-thread server system.
- If multiple threads access different objects, such as the different file, there will be no conflict.
- Copy, cache, transaction technologies in parallel system can be used in Linux kernel too, such as the per CPU cache in slab subsystem.
Scheduler for all "threads"
In operating system, not only the traditional process and thread are schedule-able entities, but also the IRQ handler, software IRQ, tasklet, timer operations and work queue should be the schedule-able entities too, conceptually.
Some threads can have higher priority than some tasklets, so, it can preempt these tasklets. It can even have higher priority than some IRQ handler, so that the IRQ is not serviced during thread executing. I think this is a useful concept in real-time system. I think the thread-style IRQ handing in FreeBSD maybe follow the same concept.
Some threads can have higher priority than some tasklets, so, it can preempt these tasklets. It can even have higher priority than some IRQ handler, so that the IRQ is not serviced during thread executing. I think this is a useful concept in real-time system. I think the thread-style IRQ handing in FreeBSD maybe follow the same concept.
Video pipeline
- Video capture
- Analog video
- Tuner
- ADC
- Analog video decoder (PAL, NTSC)
- Digital video
- Digital tuner
- Demodulating
- Demux
- Decoder
- Video processing
- Video clip
- Video scaling
- Video scan type/scan rate conversion
- Frame/field rate conversion
- Interleaved -> progressive, progressive -> interleaved
- Color space conversion
- RGB -> YUV
- YUV -> RGB
- Brightness, contrast, Hue/Tint, color temperature conversion
- Video enhancement
- Histogram equilization
- Flesh tone correction
- Noise reduction
- Video blending
- Chroma keying
- video mixer
- Video display
- Gamma correction
- Converting to panel signal format (Panel timing control)
Cancelable operations
There are many cancelable operations in software system with user interaction, such as cancel auto tunning in TV. The implementation mechanisms of cancelable operations are as follow:
Problems:
- message
The "cancel" message is sent to thread which do long-time job if necessary. While the function which do long-time job must check whether there are "cancel" message received, if so, the function must stop working and return.
Cons:
- It isn't native programming model in Linux/Unix, so third party software will not use it.
- Can't cancel work in kernel (for example the sleep or block read can not be interrupted)
- signal / real time signal
The "cancel" signal is sent to thread which do long-time job if neccesary. Upon the signal is received, the blocked operation (such as sleep, blocked read, etc) will be interrupted and a signal action function will be called which set a flag to indicate the canel signal is received by the thread. The function which do long-time job must check the flag to see whether there are "cancel" signal received, if so, the function must stop working and return.
Pros:
- Native programming model in Linux/Unix, easy to cooperate with third party software.
- Can cancel work in kernel.
Problems:
- race conditions !!!
Subscribe to:
Posts (Atom)