FEED Validator

for Atom and RSS and KML

Congratulations!

This is a valid Atom 1.0 feed.

Recommendations

This feed is valid, but interoperability with the widest range of feed readers could be improved by implementing the following recommendations.

line 72, column 0: Non-html tag: stdlib.h (5 occurrences) [help]
```
#include <stdlib.h> 
```

line 309, column 0: content should not contain script tag [help]

<script src="https://gist.github.com/6489019.js"></script><noscript><pre><co ...

line 345, column 0: content should not contain fetchpriority attribute [help]

<p><a href="http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004.jp ...

line 345, column 0: content should not contain decoding attribute (50 occurrences) [help]
```
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004.jp ...
```
line 345, column 0: content should not contain sizes attribute (17 occurrences) [help]
```
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004.jp ...
```
line 364, column 0: content should not contain aria-describedby attribute (6 occurrences) [help]
```
<div id="attachment_138" style="width: 310px" class="wp-caption alignnone">< ...
```
line 371, column 0: content should not contain loading attribute (39 occurrences) [help]
```
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle2.png">< ...
```
line 374, column 0: style attribute contains potentially dangerous content: vertical-align: -3px; (11 occurrences) [help]
```
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-cont ...
```

line 631, column 0: Invalid HTML: malformed start tag, at line 79, column 60 [help]

  4004c3:       74 06                   je     4004cb <main+0x17><br />

Source: http://samueldotj.com/blog/?feed=atom

<?xml version="1.0" encoding="UTF-8"?><feed
xmlns="http://www.w3.org/2005/Atom"
xmlns:thr="http://purl.org/syndication/thread/1.0"
xml:lang="en-US"
>
<title type="text">Samuel Jacob's Weblog</title>
<subtitle type="text">Just another technical blog</subtitle>
<updated>2015-09-12T04:51:24Z</updated>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog" />
<id>http://samueldotj.com/blog/feed/atom/</id>
<link rel="self" type="application/atom+xml" href="http://samueldotj.com/blog/feed/atom/" />
<generator uri="https://wordpress.org/" version="6.5.3">WordPress</generator>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[SWIG and Complex C structures]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/swig-and-complex-c-structures/" />
<id>http://samueldotj.com/blog/?p=231</id>
<updated>2015-09-12T04:51:24Z</updated>
<published>2015-09-12T04:51:24Z</published>
<category scheme="http://samueldotj.com/blog" term="C" /><category scheme="http://samueldotj.com/blog" term="Programming" />
<summary type="html"><![CDATA[I had to use SWIG to access a kernel module’s chardev interface through python and found SWIG examples are not enough, so adding my own. Lets take the following example header file. I will explain how to access all the members in complex_struct_t from python. Also extend these structures so that python code would look […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/swig-and-complex-c-structures/"><![CDATA[I had to use SWIG to access a kernel module’s chardev interface through python and found SWIG examples are not enough, so adding my own.
Lets take the following example header file. 
I will explain how to access all the members in complex_struct_t from python. 
Also extend these structures so that python code would look little better. 
[codegroup] 
[c tab=”header”]
/* test.h */
#ifndef _TEST_STRUCT_H 
#define _TEST_STRUCT_H
/* a simple structure – no problem with SWIG */ 
typedef struct simple_struct { 
int int_var; 
long long_var; 
float float_var; 
} simple_struct_t;
typedef struct tlv_base { 
int type; 
int length; 
unsigned char value[]; 
} tlv_base_t;
typedef struct tlv_type1 { 
tlv_base_t base; 
int stat; 
int info; 
long something; 
} tlv_type1_t;
/* relatively complex C structure. */ 
typedef struct complex_struct { 
char string[10]; //SWIG considers this as null terminated string 
unsigned char bytes[10]; //SWIG wont considers this as string
 simple_struct_t embedded;
 int pointer_array_count; 
simple_struct_t *pointer_array; //SWIG supports only accessing first element.
 tlv_base_t tlv; //How do cast this to derived_struct_1 ? 
} complex_struct_t;
complex_struct_t * alloc_complex_struct(int array_count); 
void free_complex_struct(complex_struct_t *cs); 
void print_complex_struct(complex_struct_t *cs);
#endif 
[/c]
[c tab=’source’]
/* test.c */
#include <stdlib.h> 
#include <stdio.h>
#include “test.h”
complex_struct_t * 
alloc_complex_struct(int array_count) 
{ 
complex_struct_t *result; 
size_t size;
 result = (complex_struct_t *)malloc(sizeof(complex_struct_t) + sizeof(tlv_type1_t)); 
if (result == NULL){ 
return NULL; 
}
 result->tlv.type = 1; 
result->tlv.length = sizeof(tlv_type1_t);
 size = sizeof(simple_struct_t) * array_count; 
result->pointer_array = (simple_struct_t *)malloc(size); 
if (result->pointer_array == NULL) { 
free(result); 
return NULL; 
} 
memset(result->pointer_array, 0, size); 
result->pointer_array_count = array_count;
 return result; 
}
void 
free_complex_struct(complex_struct_t *cs) 
{ 
free(cs->pointer_array); 
free(cs); 
}
static inline void 
print_simple_struct(simple_struct_t *ss) 
{ 
printf(“int %d long %ld float %f\n”, ss->int_var, ss->long_var, ss->float_var); 
}
void 
print_complex_struct(complex_struct_t *cs) 
{ 
int i;
 printf(“String = %s\n”, cs->string); 
printf(“Embedded : “); 
print_simple_struct(&cs->embedded); 
printf(“External : \n”); 
for (i=0; i<cs->pointer_array_count; i++) { 
printf(“%d) “, i + 1); 
print_simple_struct(&cs->pointer_array[i]); 
} 
}
[/c]
[raw tab=’interface’] 
// test_swig.i 
%module test_struct 
%{ 
#include “../test.h” 
%}
%include “test.h” 
[/raw]
[shell tab=’commands’] 
# Commands to make the shared library 
$ mkdir -p _build 
$ gcc -I /usr/include/python2.7/ -fPIC -c -o _build/test.o test.c 
$ swig -python -outdir _build -o _build/test_swig_wrap.c test_swig.i 
$ gcc -I /usr/include/python2.7/ -fPIC -c -o _build/test_swig_wrap.o _build/test_swig_wrap.c 
$ ld -shared _build/test.o _build/test_swig_wrap.o -o _build/_test_struct.so 
$ rm _build/test_swig_wrap.c 
[/shell]
[raw tab=’makefile’] 
#Makefile 
BLD_DIRECTORY = _build
SWIG_SRCS = test_swig.i 
C_SRCS = test.c 
CFLAGS = -I /usr/include/python2.7/ -fPIC -c -Wall
OBJS = $(patsubst %.c, $(BLD_DIRECTORY)/%.o, $(C_SRCS)) \ 
$(patsubst %.i, $(BLD_DIRECTORY)/%_wrap.o, $(SWIG_SRCS))
$(BLD_DIRECTORY)/%.o: %.c %.h 
gcc $(CFLAGS) -o $@ $<
$(BLD_DIRECTORY)/%.o: $(BLD_DIRECTORY)/%.c 
gcc $(CFLAGS) -o $@ $<
$(BLD_DIRECTORY)/%_wrap.c: %.i 
swig -python -outdir $(BLD_DIRECTORY) -o $@ $< 
cp $@ $@.bak
$(BLD_DIRECTORY): 
mkdir -p $(BLD_DIRECTORY)
clean: 
rm -rf $(BLD_DIRECTORY)
all: $(BLD_DIRECTORY) $(OBJS) $(C_SRCS) $(SWIG_SRCS) 
ld -shared $(OBJS) -o $(BLD_DIRECTORY)/_test_struct.so
.PHONY: all clean
.DEFAULT_GOAL := all 
[/raw] 
[/codegroup]
With this simple interface file, SWIG would be able to create a _test_struct.so and test_struct.py which is perfect for most cases. 
[raw tab=’interface’] 
%module test_struct 
%{ 
#include “../test.h” 
%}
%include “test.h” 
[/raw]
[python] 
import test_struct as ts 
cs = ts.alloc_complex_struct(1) 
cs.string = “Hello” 
cs.embedded.int_var = 9 
cs.embedded.long_var = 10 
cs.embedded.float_var = 11.23 
ts.print_complex_struct(cs) 
ts.free_complex_struct(cs) 
[/python]
This shows SWIG’s ability to convert C string to python string and vice versa. 
Similarly accessing primitive structure members is very easy. 
Here is the output of the program when ran from _build directory. 
[raw] 
String = Hello 
Embedded : int 9 long 10 float 11.230000 
Pointer Array : 
1) int 0 long 0 float 0.000000 
[/raw]
It also shows how to call function call into C library. If you have noticed this program looks more like a C program rather than a python program – mainly because it manages the memory allocation/free. Python can informed that [c] alloc_complex_struct() [/c] returns a new object and it is the responsibility of the caller to free it by using the SWIG typemap [python] newobject [/python]. Now python garbage collector will free the object when there is no reference. But python does not know how to free the object(complex_struct_t) – this can be done by using [python]newfree[/python] typemap.
By adding the following to the test_swig.i, we can avoid calling free_complex_struct() in python program. 
[c] 
%typemap(newobject) alloc_complex_struct; 
%typemap(newfree) complex_struct_t * { 
free_complex_struct($1); 
} 
[/c]
Lets modify the program a little bit and access the pointer_array elements.
[python] 
import test_struct as ts 
cs = ts.alloc_complex_struct(5) 
print ‘Pointer array count ‘, cs.pointer_array_count 
print cs.pointer_array[0] 
ts.free_complex_struct(cs) 
[/python]
This will fail with the following error: 
[raw] 
Pointer array count 5 
Traceback (most recent call last): 
File “./test.py”, line 4, in <module> 
print cs.pointer_array[0] 
TypeError: ‘simple_struct_t’ object does not support indexing 
[/raw]
The reason is SWIG does not really know [c]simple_struct_t *pointer_array;[/c] actually points to an array of [c]simple_struct_t[/c]. In other words SWIG safely assumes it points to a single entry. If pointer_array was “array of simple_struct_t pointers” then <a href="http://www.swig.org/Doc3.0/SWIGDocumentation.html#Library_carrays" target="_blank">carrays.i</a> macro would have been helped. But pointer_array is actually “pointer to array of simple_struct_t” so carrays.i won’t help.
The easiest way is extending complex_struct_t and add a new member(kind of) function to it. 
[c] 
%extend complex_struct_t{ 
simple_struct_t *get_array_element(int i) { 
return &$self->pointer_array[i]; 
} 
} 
[/c]
This way cs.get_array_element(4) will return 4th element in the array. 
Similarly tlv elements can be accessed also – but this time I decided to override indexing operator([]).
[c] 
%extend complex_struct_t{ 
unsigned char __getitem__(int i) { 
return $self->tlv[i]; 
} 
} 
[/c]
However this is not useful since python cant cast from [c](struct tlv_base *)[/c] to [c]struct tlv_type1 *[/c]. To cast, a C function can be coded or SWIG’s cpointer.i can be used.
Here is the full test_swig.i 
[c] 
%module test_struct 
%{ 
#include “../test.h” 
%} 
%include “test.h” 
%extend complex_struct{ 
simple_struct_t *get_array_element(int i) { 
return &$self->pointer_array[i]; 
} 
} 
%typemap(newobject) alloc_complex_struct; 
%typemap(newfree) complex_struct_t * { 
free_complex_struct($1); 
} 
%include <cpointer.i> 
%pointer_cast(tlv_base_t *, tlv_type1_t *, cast_to_tlv_type1); 
[/c]
And test code: 
[python] 
import test_struct as ts 
cs = ts.alloc_complex_struct(5) 
cs.string = ‘Hello’ 
print ‘Pointer array count ‘, cs.pointer_array_count 
for i in range(cs.pointer_array_count): 
simple_struct = cs.get_array_element(i) 
simple_struct.int_var = i * 10 
simple_struct.long_var = i * 20 
simple_struct.float_var = i * 3.3 
ts.print_complex_struct(cs) 
tlv = ts.cast_to_tlv_type1(cs.tlv) 
print tlv.stat, tlv.info, tlv.something 
[/python]
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[I2C 20×4 LCD module and Arduino]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/i2c-20x4-lcd-module-and-arduino/" />
<id>http://samueldotj.com/blog/?p=204</id>
<updated>2013-09-08T23:12:24Z</updated>
<published>2013-09-08T23:12:01Z</published>
<category scheme="http://samueldotj.com/blog" term="Uncategorized" /><category scheme="http://samueldotj.com/blog" term="Arduino" />
<summary type="html"><![CDATA[Recently I was working on a ZigBee project using XBee. Since XBee occupied the Arduino UART port, I decided use a character LCD for debug logs. I got the SainSmart 20×4 LCD module with i2c interface. The connections are simple: Arduino LCD 5v VCC GND GND SDA A5/SDA SCL A4/SCL But I couldnt make it […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/i2c-20x4-lcd-module-and-arduino/"><![CDATA[Recently I was working on a ZigBee project using XBee. Since XBee occupied the Arduino UART port, I decided use a character LCD for debug logs. I got the <a href="http://www.sainsmart.com/sainsmart-iic-i2c-twi-serial-2004-20x4-lcd-module-shield-for-arduino-uno-mega-r3.html">SainSmart 20×4 LCD module</a> with i2c interface. The connections are simple: 
<table class="gridtable">
<tr>
<th>Arduino</th>
<th>LCD</th>
</tr>
<tr>
<td>5v</td>
<td>VCC</td>
</tr>
<tr>
<td>GND</td>
<td>GND</td>
</tr>
<tr>
<td>SDA</td>
<td>A5/SDA</td>
</tr>
<tr>
<td>SCL</td>
<td>A4/SCL</td>
</tr>
</table>
But I couldnt make it work with sample code provided, after few googling I found that the sample code has a wrong i2c address. Even after using the correct I2C address(0x3f), it didnt work, but I was getting only to horizontal black bars on the screen. 
I confirmed the I2C is working by using I2C Explorer. Finally after updating the i2c <a href="https://bitbucket.org/fmalpartida/new-liquidcrystal/wiki/Home">library</a> and with the following code, it started working. I found this code on a amazon review and modified for my purpose.
<script src="https://gist.github.com/6489019.js"></script><noscript><pre><code class="language-c c">/*
* Sample code for SainSmart IIC/I2C/TWI Serial 2004 20x4 LCD Module.
* License: GPL
*/
#include <Wire.h>
#include <LiquidCrystal_I2C.h>
#define I2C_ADDR 0x3F
#define En_pin 2
#define Rw_pin 1
#define Rs_pin 0
#define D4_pin 4
#define D5_pin 5
#define D6_pin 6
#define D7_pin 7
#define BACKLIGHT_PIN 3
LiquidCrystal_I2C lcd(I2C_ADDR, En_pin, Rw_pin, Rs_pin,
D4_pin, D5_pin, D6_pin, D7_pin);
void setup() {
lcd.begin (20, 4);
// Switch on the backlight
lcd.setBacklightPin(BACKLIGHT_PIN, POSITIVE);
lcd.setBacklight(LOW);
// Position cursor and write some text
lcd.home();
lcd.print("Hello World");
}
void loop() {
}
</code></pre></noscript>
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004.jpg"><img fetchpriority="high" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004-300x200.jpg" alt="LCD2004" width="300" height="200" class="alignnone size-medium wp-image-216" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004-300x200.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2013/09/LCD2004-1024x682.jpg 1024w" sizes="(max-width: 300px) 100vw, 300px" /></a>
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[Fix loop in a linked list]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/fix-loop-in-a-linked-list/" />
<id>http://samueldotj.com/blog/?p=134</id>
<updated>2013-08-29T22:35:33Z</updated>
<published>2013-08-29T22:35:33Z</published>
<category scheme="http://samueldotj.com/blog" term="Uncategorized" />
<summary type="html"><![CDATA[Cycle or loop in a linked list with nodes is shown in pictorial representation. In this picture the number of nodes in the list is and the last node points to node at a position x(which created the cycle). From the picture it is obvious that to fix the loop: Find the last element Correct […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/fix-loop-in-a-linked-list/"><![CDATA[Cycle or loop in a linked list with <img decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-9f9c792f3d1c0d436f1e9ae9ff2e4949_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n" title="Rendered by QuickLaTeX.com" height="7" width="10" style="vertical-align: 0px;"/> nodes is shown in pictorial representation. 
<div id="attachment_138" style="width: 310px" class="wp-caption alignnone"><a href="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle.png"><img decoding="async" aria-describedby="caption-attachment-138" src="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle-300x65.png" alt="Loop in a singly linked list" width="300" height="65" class="size-medium wp-image-138" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle-300x65.png 300w, http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle.png 583w" sizes="(max-width: 300px) 100vw, 300px" /></a>Loop in a singly linked list</div>
In this picture the number of nodes in the list is <img decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-9f9c792f3d1c0d436f1e9ae9ff2e4949_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n" title="Rendered by QuickLaTeX.com" height="7" width="10" style="vertical-align: 0px;"/> and the last node points to node at a position x(which created the cycle). From the picture it is obvious that to fix the loop:
<ol>
<li>Find the last element</li>
<li>Correct it to point end(NULL)</li>
</ol>
In the above steps, step 1(find the last element) is little difficult if total number of nodes in the list is unknown. In this post I will describe a method I discovered to find the last node. I drew couple of pictures to explain the complexity of the problem. The following pictures explains the same loop condition but in different form. It explains why it is hard to find the last node. 
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle2.png"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle2.png" alt="Cycle2" width="635" height="91" class="alignnone size-full wp-image-151" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle2.png 635w, http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle2-300x42.png 300w" sizes="(max-width: 635px) 100vw, 635px" /></a>
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle3.png"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle3.png" alt="Cycle3" width="469" height="108" class="alignnone size-full wp-image-152" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle3.png 469w, http://samueldotj.com/blog/wp-content/uploads/2013/08/Cycle3-300x69.png 300w" sizes="(max-width: 469px) 100vw, 469px" /></a> 
The illustration also tells us the following 
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-9b30a924495e1f93eff66310347f2ac0_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n = x+y" title="Rendered by QuickLaTeX.com" height="14" width="71" style="vertical-align: -3px;"/> 
where 
  <img decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-9f9c792f3d1c0d436f1e9ae9ff2e4949_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="n" title="Rendered by QuickLaTeX.com" height="7" width="10" style="vertical-align: 0px;"/> is total number of nodes in the list 
  <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-8aa17fa6615962eb1a747b73bcc92f80_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x" title="Rendered by QuickLaTeX.com" height="7" width="9" style="vertical-align: 0px;"/> is number of nodes before the cycle starts. 
  <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-5f08a280df35506f9363e0d1703cd851_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="y" title="Rendered by QuickLaTeX.com" height="10" width="9" style="vertical-align: -3px;"/> is number of nodes forming the cycle.
If we have value of <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-8aa17fa6615962eb1a747b73bcc92f80_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x" title="Rendered by QuickLaTeX.com" height="7" width="9" style="vertical-align: 0px;"/> and <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-5f08a280df35506f9363e0d1703cd851_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="y" title="Rendered by QuickLaTeX.com" height="10" width="9" style="vertical-align: -3px;"/> then the equation can be solved, which will give the last node’s location.
Finding <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-5f08a280df35506f9363e0d1703cd851_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="y" title="Rendered by QuickLaTeX.com" height="10" width="9" style="vertical-align: -3px;"/>
<ol>
<li>Detect the cycle using Floyd’s Cycle detection algorithm. (Two pointer with varying speed)</li>
<li>When cycle is detected
<ol>
<li>Store the current node as H</li>
<li>Move to next node and increment y(y++)</li>
<li>If current node is H then exit</li>
<li>Goto step 2</li>
</ol>
</li>
</ol>
Finding <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-8aa17fa6615962eb1a747b73bcc92f80_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x" title="Rendered by QuickLaTeX.com" height="7" width="9" style="vertical-align: 0px;"/> 
Let’s first see the easiest way to solve this:
<ol>
<li>Have two pointers (p1, p2)</li>
<li>p1 = node 0</li>
<li>p2 = p1 + y nodes</li>
<li>if p1 == p2 then we found the result is <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-6f2ecc48c4d5bf5138ee701167a61b2d_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x = p1" title="Rendered by QuickLaTeX.com" height="15" width="47" style="vertical-align: -3px;"/></li>
<li>p1 = p1 + y nodes</li>
<li>goto step 3.</li>
</ol>
The complexity of this algorithm linear depends on <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-8aa17fa6615962eb1a747b73bcc92f80_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x" title="Rendered by QuickLaTeX.com" height="7" width="9" style="vertical-align: 0px;"/>. For example if <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-8aa17fa6615962eb1a747b73bcc92f80_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x" title="Rendered by QuickLaTeX.com" height="7" width="9" style="vertical-align: 0px;"/> is 10K and <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-5f08a280df35506f9363e0d1703cd851_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="y" title="Rendered by QuickLaTeX.com" height="10" width="9" style="vertical-align: -3px;"/> is 2 then number of node visits are > 20K. In other words the complexity is <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-be009ed84c5dbef8c9da4e0ab80612af_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="O(2x + y)" title="Rendered by QuickLaTeX.com" height="18" width="72" style="vertical-align: -4px;"/>.
I believe it can be done in <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-f17985b51fa15d9e24ccb364fde3fe90_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="O(n)" title="Rendered by QuickLaTeX.com" height="18" width="34" style="vertical-align: -4px;"/> or <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-5a4d08945942ad313f7a743439496291_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="O(x + y)" title="Rendered by QuickLaTeX.com" height="18" width="63" style="vertical-align: -4px;"/> with following method This following diagram captures state when the “tortoise and the hare” algorithm detects the cycle.
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/08/CycleFix1.png"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2013/08/CycleFix1.png" alt="CycleFix" width="506" height="130" class="alignnone size-full wp-image-159" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/08/CycleFix1.png 506w, http://samueldotj.com/blog/wp-content/uploads/2013/08/CycleFix1-300x77.png 300w" sizes="(max-width: 506px) 100vw, 506px" /></a>
Lets define few more variables at the time of cycle detection: 
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-2f2cb00cf96aa920ab1041073bf8ad6a_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="T" title="Rendered by QuickLaTeX.com" height="11" width="12" style="vertical-align: 0px;"/> is the total number of nodes tortoise traveled. 
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-a6f2b49d15c8a555a5b861c560881b92_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="H" title="Rendered by QuickLaTeX.com" height="11" width="15" style="vertical-align: 0px;"/> is the total number of nodes hare traveled. 
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-2650c16c3c9e38aa51f9867a23890025_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="r" title="Rendered by QuickLaTeX.com" height="7" width="8" style="vertical-align: 0px;"/> can be defined as number of nodes before the ‘last node’
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-c70da08357ecd9bf6af83d7b204b158d_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="T = 2H \newline x + cy - r = T \newline x + y - r = H \newline" title="Rendered by QuickLaTeX.com" height="56" width="108" style="vertical-align: 18px;"/>
where c is the number of complete cycles hare covered. 
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-e517549f49202880dd0ee979796fe948_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="T > H \newline c > 1 \newline r >= x \ and \ r <= n \newline" title="Rendered by QuickLaTeX.com" height="52" width="144" style="vertical-align: 21px;"/>
From this we can derive 
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-322906623d83aeb0b7cd20ba5f67f2ea_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="c = H / y + 1" title="Rendered by QuickLaTeX.com" height="16" width="88" style="vertical-align: -4px;"/>
Using value of <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-9fbeb23be22f99c93f330d0033c50568_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="c" title="Rendered by QuickLaTeX.com" height="7" width="8" style="vertical-align: 0px;"/>, <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-2650c16c3c9e38aa51f9867a23890025_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="r" title="Rendered by QuickLaTeX.com" height="7" width="8" style="vertical-align: 0px;"/> can be derived.
<img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-cb01f9fc40f4d1767f4ea1db4dd72fc4_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="x + y - r = H \newline r = x + y - H \newline \newline x + cy - r = T \newline x = T - cy + r \newline \newline r = T - cy + r + y - H \newline r = H - cy + r + y \newline" title="Rendered by QuickLaTeX.com" height="159" width="171" style="vertical-align: 18px;"/>
Using this formula <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-2650c16c3c9e38aa51f9867a23890025_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="r" title="Rendered by QuickLaTeX.com" height="7" width="8" style="vertical-align: 0px;"/> can be found. With this <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-2650c16c3c9e38aa51f9867a23890025_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="r" title="Rendered by QuickLaTeX.com" height="7" width="8" style="vertical-align: 0px;"/> value, the last node can be found by travelling <img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/ql-cache/quicklatex.com-0dfe30d9edc6651a2b70a0afb7f6828f_l3.png" class="ql-img-inline-formula quicklatex-auto-format" alt="r-1" title="Rendered by QuickLaTeX.com" height="13" width="35" style="vertical-align: -1px;"/> nodes where T and H met.
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[LLDB Backtrace formatting]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/lldb-backtrace-formatting/" />
<id>http://samueldotj.com/blog/?p=4</id>
<updated>2013-08-26T23:25:45Z</updated>
<published>2013-07-23T04:20:00Z</published>
<category scheme="http://samueldotj.com/blog" term="C" /><category scheme="http://samueldotj.com/blog" term="Debugger" /><category scheme="http://samueldotj.com/blog" term="lldb" />
<summary type="html"><![CDATA[lldb can be configured to print backtraces with syntax highlighting. Here is how to setup lldb to do that Consider the following source level debugging session, [codegroup] [c tab=’source’] $ cat test.c static void crash_me() { char *c = 0; *c = 0; } static void recursive_call(int value) { if (value == 0) { crash_me(); […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/lldb-backtrace-formatting/"><![CDATA[lldb can be configured to print backtraces with syntax highlighting. Here is how to setup lldb to do that
Consider the following source level debugging session, 
[codegroup] 
[c tab=’source’] 
$ cat test.c 
static void crash_me() 
{ 
char *c = 0; 
*c = 0; 
}
static void recursive_call(int value) 
{ 
if (value == 0) { 
crash_me(); 
} 
recursive_call(value – 1); 
}
int main(int argc, char argv[]) 
{ 
recursive_call(argc); 
} 
[/c] 
[shell tab=’commands’] 
$ gcc -g3 -O3 test.c 
$ lldb a.out 
(lldb) run 0 1 2 3 4 5 
[/shell] 
[/codegroup]
Without color syntax the backtrace would look like the following. 
<div id="attachment_127" style="width: 310px" class="wp-caption alignnone"><a href="http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-nocolor.png"><img loading="lazy" decoding="async" aria-describedby="caption-attachment-127" src="http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-nocolor-300x98.png" alt="Normal backtrace with out any makeup" width="300" height="98" class="size-medium wp-image-127" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-nocolor-300x98.png 300w, http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-nocolor-1024x337.png 1024w, http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-nocolor.png 1841w" sizes="(max-width: 300px) 100vw, 300px" /></a>Normal backtrace with out any makeup</div>
Since lldb supports ANSI escape sequence, the escape sequences can be used to color the backtrace output which makes output more readable. Here is the link to official lldb page describing this feature – <a href='http://lldb.llvm.org/formats.html'>http://lldb.llvm.org/formats.html</a>.
Here is my backtrace setting and example
[shell] 
(lldb) settings set frame-format “frame #${frame.index}: ${frame.pc}{ \x1b\x5b36m${module.file.basename}\x1b\x5b39m{` \x1b\x5b33m${function.name-with-args} \x1b\x5b39m${function.pc-offset}}}{ at ${line.file.basename}:${line.number}}\n”
[/shell] 
<div id="attachment_125" style="width: 310px" class="wp-caption alignnone"><a href="http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-color.jpg"><img loading="lazy" decoding="async" aria-describedby="caption-attachment-125" src="http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-color-300x53.jpg" alt="Backtrace with color" width="300" height="53" class="size-medium wp-image-125" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-color-300x53.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-color-1024x181.jpg 1024w, http://samueldotj.com/blog/wp-content/uploads/2013/07/lldb-color.jpg 1841w" sizes="(max-width: 300px) 100vw, 300px" /></a>Backtrace with color</div>
Similarly thread format cant be colorized so that ‘thread list‘ would look neat.
[shell] 
(lldb) settings set thread-format “\x1b\x5b42;1mthread #${thread.index}: tid = ${thread.id}{, ${frame.pc}}{ \x1b\x5b31m${module.file.basename}\x1b\x5b39m{`${function.name-with-args}${function.pc-offset}}}{ at ${line.file.basename}:${line.number}}{, name = ‘\x1b\x5b34m${thread.name}}\x1b\x5b39m{, queue = ‘${thread.queue}}{, stop reason = ${thread.stop-reason}}{\nReturn value: ${thread.return-value}}\x1b\x5b0m\n”
[/shell]
Reference to ANSI escape sequence – <a href="http://ascii-table.com/ansi-escape-sequences.php">http://ascii-table.com/ansi-escape-sequences.php</a>
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[Self Balancing Tree as Heap]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/self-balancing-tree-as-heap/" />
<id>http://samueldotj.com/blog/?p=5</id>
<updated>2013-08-27T01:57:59Z</updated>
<published>2013-05-11T18:59:00Z</published>
<category scheme="http://samueldotj.com/blog" term="Ace" />
<summary type="html"><![CDATA[Here is my thoughts about how to combine a Heap and AVL tree and get benefit of both them from a single data structure. A self balancing binary search tree such as AVL tree can do faster lookup for a item in the tree in O(log n). Heaps are mainly used to implement priority queues which […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/self-balancing-tree-as-heap/"><![CDATA[Here is my thoughts about how to combine a <a href='http://en.wikipedia.org/wiki/Heap_(data_structure)'>Heap</a> and <a href='http://en.wikipedia.org/wiki/AVL_tree'>AVL tree</a> and get benefit of both them from a single data structure.
A <a href="http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree">self balancing binary search tree</a> such as <a href="http://en.wikipedia.org/wiki/AVL_tree">AVL tree</a> can do faster lookup for a item in the tree in O(log n). <a href="http://en.wikipedia.org/wiki/Heap_(data_structure)">Heap</a>s are mainly used to implement priority queues which needs to find min/max elements quickly. Heap achieves this in O(1) time complexity.
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/05/Balanced-BST11.png"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2013/05/Balanced-BST11-300x204.png" alt="Balanced BST1" width="300" height="204" class="alignright size-medium wp-image-57" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/05/Balanced-BST11-300x204.png 300w, http://samueldotj.com/blog/wp-content/uploads/2013/05/Balanced-BST11.png 476w" sizes="(max-width: 300px) 100vw, 300px" /></a> Lets revisit a basic property of binary search tree – In a binary search tree min element is at the left most leaf position. Similarly in a BST max element is at the right most leaf position. So finding min/max element in a BST is O(h) where h is the depth of the tree. If the BST is a balanced tree then O(h) is O(log n) in worst case(otherwise the worst case O(n), since we considering only balanced trees here lets ignore the unbalanced cases). The following diagram illustrates a basic property of the BST – min element is always on the left most node.
<div id="attachment_64" style="width: 310px" class="wp-caption alignleft"><a href="http://samueldotj.com/blog/wp-content/uploads/2013/05/BST-PointerToMin1.png"><img loading="lazy" decoding="async" aria-describedby="caption-attachment-64" src="http://samueldotj.com/blog/wp-content/uploads/2013/05/BST-PointerToMin1-300x204.png" alt="Cached pointer to Min element at the root" width="300" height="204" class="size-medium wp-image-64" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/05/BST-PointerToMin1-300x204.png 300w, http://samueldotj.com/blog/wp-content/uploads/2013/05/BST-PointerToMin1.png 473w" sizes="(max-width: 300px) 100vw, 300px" /></a>Cached pointer to Min element at the root</div> Using this basic property, min remove operation can be optimized. The first and simplest optimization comes to mind is store a pointer to min/max elements. This caching will result in O(1) time complexity for finding min/max elements. However this would increase the cost of node insert/delete because the min/max pointer has to be updated during insert and deletion. The cost of finding and deleting a min node is O(log(n)) which is same as if we havent had the cache pointers. The picture in the right shows advantage of having cached pointer to find a min element. Obviously this method cant be used for priority queues where find min/delete operation is used together.
In the above method the problem was the complexity finding next smallest element in the tree from min element is O(log n). So if we have pointer to next smallest element from all nodes then find and delete opearation would be of complexity O(1).
Lets look at the BST from slightly different angle. Usual declaration of BST in C as follows:
[c] 
struct binary_tree 
{ 
struct binary_tree *left; 
struct binary_tree *right; 
}; 
[/c]
When we(me and <a href="http://plus.google.com/105622177928011443688" target="_blank">+Dilip Simha</a>) were implementing ADT for AceOS we decided to experiment BST in a different way. We saw tree as recursive lists rather than a recursive pointers. 
In the following picture you could see 6 lists(not counting sub-lists): 
<a href="http://samueldotj.com/blog/wp-content/uploads/2013/05/Balanced-BST12.png"><img decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2013/05/Balanced-BST12.png" alt="A list is highlighted" class="alignright size-medium wp-image-62" width="220" /></a>
<ol>
<li>(300, 200, 100, 50)</li>
<li>(300, 400, 500, 600)</li>
<li>(200, 250, 275)</li>
<li>(100, 150)</li>
<li>(400, 350)</li>
<li>(500, 450)</li>
</ol>
Now consider this list is a doubly linked circular list. This is illustrated in the following figure. You may argue that this will make the BST to become cyclic directed graph. But for the sake of simplicity lets continue to call this as balanced BST. In the picture I left out few arrows to keep it cleaner.
<div id="attachment_63" style="width: 483px" class="wp-caption aligncenter"><a href="http://samueldotj.com/blog/wp-content/uploads/2013/05/Binary-Search-Tree-Doule-Pointer.png"><img loading="lazy" decoding="async" aria-describedby="caption-attachment-63" src="http://samueldotj.com/blog/wp-content/uploads/2013/05/Binary-Search-Tree-Doule-Pointer.png" alt="Binary Search Tree with nodes having pointer to parent also" width="473" height="324" class="size-full wp-image-63" srcset="http://samueldotj.com/blog/wp-content/uploads/2013/05/Binary-Search-Tree-Doule-Pointer.png 473w, http://samueldotj.com/blog/wp-content/uploads/2013/05/Binary-Search-Tree-Doule-Pointer-300x205.png 300w" sizes="(max-width: 473px) 100vw, 473px" /></a>Binary Search Tree with nodes having pointer to parent also</div>
[c] 
typedef struct list LIST, * LIST_PTR; 
struct list { 
LIST_PTR next; 
LIST_PTR prev; 
};
typedef struct binary_tree 
{ 
LIST left; 
LIST right; 
}BINARY_TREE;
typedef struct avl_tree 
{ 
int height; /*! height of the node*/ 
BINARY_TREE bintree; /*! low level binary tree*/ 
}AVL_TREE; 
[/c]
AVL tree in Ace OS is implemented in this way. You can see the data structure declarations below. Initially we did it for reusing the code. But after implementing this we figured out some interesting properties. This balanced tree/graph can find any node in O(log(n)) and also offers findmin operation in O(1) complexity. This also reduces the complexity of delete operation(since we can find right node’s left most child in O(1) operation). But delete operation might result in balancing the tree.
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[Internals of GNU Code Coverage – gcov]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/gcov-internals-overview/" />
<id>http://samueldotj.com/blog/?p=6</id>
<updated>2013-09-08T23:18:45Z</updated>
<published>2012-03-31T23:21:00Z</published>
<category scheme="http://samueldotj.com/blog" term="C" /><category scheme="http://samueldotj.com/blog" term="gcc" /><category scheme="http://samueldotj.com/blog" term="Tools" />
<summary type="html"><![CDATA[Few years ago I worked on a small project to extract code coverage information created by gcc from FreeBSD based kernel. During that time I didn’t find any good internal documentation about gcov. So here I post what I learned. Before jumping to the internals of GCOV here is an example from the man page. […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/gcov-internals-overview/"><![CDATA[Few years ago I worked on a small project to extract <a href="http://en.wikipedia.org/wiki/Code_coverage">code coverage</a> information created by gcc from FreeBSD based <a href="http://www.freebsd.org/">kernel</a>. During that time I didn’t find any good internal documentation about <a href="http://gcc.gnu.org/onlinedocs/gcc/Gcov.html">gcov</a>. So here I post what I learned. Before jumping to the internals of GCOV here is an example from the <a href="http://nixdoc.net/man-pages/openbsd/man1/gcov.1.html">man </a>page.
<pre class="code">
$ gcov -b tmp.c
87.50% of 8 source lines executed in file tmp.c
80.00% of 5 branches executed in file tmp.c
80.00% of 5 branches taken at least once in file tmp.c
50.00% of 2 calls executed in file tmp.c
Creating tmp.c.gcov.
Here is a sample of a resulting tmp.c.gcov file:
main()
{
 1 int i, total;
 1 total = 0;
 11 for (i = 0; i < 10; i++)
branch 0 taken = 91%
branch 1 taken = 100%
branch 2 taken = 100%
 10 total += i;
 1 if (total != 45)
branch 0 taken = 100%
 ###### printf ("Failure0);
call 0 never executed
branch 1 never executed
else
 1 printf ("Success0);
call 0 returns = 100%
 1 }
</pre>
Note – gcov has a cool graphical front-end in Linux – <a href="http://ltp.sourceforge.net/coverage/lcov/output/example/example.c.gcov.frameset.html">lcov</a>. 
As shown above gcov can show what all code path executed and how many time executed. 
Want to try? Here is the quick example. 
[shell] 
$ gcc -fprofile-arcs -ftest-coverage your_program.c 
$ ./a.out 
$ gcov your_program.c 
[/shell]
During compilation with <a href="http://gcc.gnu.org/onlinedocs/gcc/Debugging-Options.html">-ftest-coverage</a> option gcc generates a <a href="http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Gcov-Data-Files.html">“.gcno”</a> file. It contains information about each branches in your code. While finishing execution, ./a.out creates .gcda file(s) which actually contains which all branches taken(<a href='http://en.wikipedia.org/wiki/Basic_block'>basic block</a> entry/exit). Using these there files .c(source), .gcno(block info) and .gcda(block execution count) gcov command prints the code coverage information in a human readable format.
You might wonder how your ./a.out would create .gcda while exiting the program. It is because of “-fprofile-arcs” automatically includes <a href="http://gcc.gnu.org/viewcvs/trunk/libgcc/libgcov.c?view=markup">libgcov</a>. Libgcov registers itself to be invoked during program exit by using <a href="http://pubs.opengroup.org/onlinepubs/009604599/functions/atexit.html">atexit()</a>. (Yes – it wont generate .gcda files if you exit abnormally). And during program <a href="http://pubs.opengroup.org/onlinepubs/000095399/functions/exit.html">exit</a> it just dumps all the branch information to one or more gcda file.
The coverage information is “just” dumped into files by libgcov. So who collects the the coverage information at run time? Actually the program itself collects the coverage information. In-fact only it can collect because only it knew which all code path it takes. The code coverage information is collected at run-time on the fly. It is accomplished by having a counter for each branch. For example consider the following program.
<pre class="code">
int if_counter = 0, else_counter = 0;

void dump_counters()
{
int fd;
fd = open(strcat(filename, ".gcda"), "w");
write(fd, if_counter, sizeof(if_counter));
write(fd, else_counter, sizeof(else_counter));
}

int main(int argc, char *argv[])
{
atexit(dump_counters);
if(argc > 1) {
if_counter++;
printf("Arguments provided\n");
} else {
else_counter++;
printf("No arguments\n");
}
}
</pre>
If you replace the above example with gcov then green colored code is provided by libgcov(during link/load) and the blue colored coded inserted into your executable by gcc(during compilation).
It is easy to speculate how the increment operation would be be implanted inside your code by gcc. gcc just inserts “inc x-counter“ machine instruction before and after every branch. It should be noted that “inc” is instruction might have side effect on some programs which uses asm inside C. For example in x86 the “<a href="http://maven.smith.edu/~thiebaut/ArtOfAssembly/CH06/CH06-2.html#HEADING2-117">inc</a>” instruction affects <a href="http://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture#EFLAGS_Register">carry flag</a>. Some assembly code might depends on this and if gcc inserts “inc counter” instruction then it will result in error. I had hard time figuring this out when compiled with -fprofile-arcs a kernel was booting but not able to receive any network packets(it was discarding all packets because the network stack found the <a href="http://www.netfor2.com/checksum.html">checksum</a> was wrong).
Here is a simple C program’s disassembly: 
[codegroup] 
[c tab=’disassembly’] 
int main() 
{ 
4004b4: 55 push %rbp 
4004b5: 48 89 e5 mov %rsp,%rbp 
int a = 1; 
4004b8: c7 45 fc 01 00 00 00 movl $0x1,-0x4(%rbp)
 if (a) { 
4004bf: 83 7d fc 00 cmpl $0x0,-0x4(%rbp) 
4004c3: 74 06 je 4004cb <main+0x17> 
a++; 
4004c5: 83 45 fc 01 addl $0x1,-0x4(%rbp) 
4004c9: eb 04 jmp 4004cf <main+0x1b> 
} else { 
a–; 
4004cb: 83 6d fc 01 subl $0x1,-0x4(%rbp) 
}
 return a; 
4004cf: 8b 45 fc mov -0x4(%rbp),%eax 
} 
[/c]
[c tab=’source’] 
int main() 
{ 
int a = 1;
 if (a) { 
a++; 
} else { 
a–; 
}
 return a; 
} 
[/c]
[shell tab=’command’] 
gcc -g3 test.c 
objdump -S -d ./a.out 
[/shell]
[/codegroup]
When the same program compiled with profile-arcs, the disassembly looks like
<pre class="code">
int main()
{
400c34: 55 push %rbp
400c35: 48 89 e5 mov %rsp,%rbp
400c38: 48 83 ec 10 sub $0x10,%rsp
int a = 1;
400c3c: c7 45 fc 01 00 00 00 movl $0x1,-0x4(%rbp)
if (a) {
400c43: 83 7d fc 00 cmpl $0x0,-0x4(%rbp)
400c47: 74 18 je 400c61 <main+0x2d>
a++;
400c49: 83 45 fc 01 addl $0x1,-0x4(%rbp)
 400c4d: 48 8b 05 3c 25 20 00 mov 0x20253c(%rip),%rax # 603190 <dtor_idx.6460+0x8>
400c54: 48 83 c0 01 add $0x1,%rax
400c58: 48 89 05 31 25 20 00 mov %rax,0x202531(%rip) # 603190 <dtor_idx.6460+0x8>
400c5f: eb 16 jmp 400c77 <main+0x43>
} else {
a--;
400c61: 83 6d fc 01 subl $0x1,-0x4(%rbp)
 400c65: 48 8b 05 2c 25 20 00 mov 0x20252c(%rip),%rax # 603198 <dtor_idx.6460+0x10>
400c6c: 48 83 c0 01 add $0x1,%rax
400c70: 48 89 05 21 25 20 00 mov %rax,0x202521(%rip) # 603198 <dtor_idx.6460+0x10>
}
return a;
400c77: 8b 45 fc mov -0x4(%rbp),%eax
}
400c7a: c9 leaveq
400c7b: c3 retq
</pre>
From the above disassembly it might seem putting inc instruction while compiling is easy. But how/where storage for the counters(dtor_idx.6460 and dtor_idx.6460 in above example) are created. GCC uses statically allocated memory. Dynamically allocating space is one way but it would complicate the code(memory allocation operations during init) and might slow down execution of program(defer pointer). To avoid that gcc allocates storage as a loadable section.
The compiler keep tracks of all the counters in a single file. The data structure outlined in the below picture. 
<a href="http://samueldotj.com/blog/wp-content/uploads/2012/03/gcov-1.png"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2012/03/gcov-1.png" alt="gcov" width="577" height="423" class="aligncenter size-full wp-image-53" srcset="http://samueldotj.com/blog/wp-content/uploads/2012/03/gcov-1.png 577w, http://samueldotj.com/blog/wp-content/uploads/2012/03/gcov-1-300x219.png 300w" sizes="(max-width: 577px) 100vw, 577px" /></a> 
There is a single gcov_info structure for a C file. And multiple gcov_fn_info and gcov_ctr_info. During program exit() these structures are dumped into the .gcda file. For a project(with multiple C files) each C file will have a gcov_info structure. These gcov_info structures should be linked together so that during exit() the program can generate .gcda file for all the C files. This is done by using constructors and destructors.
Generic C constructor: 
gcc generates constructors for all program. C constructors are accomplished by using “.ctors” section of ELF file. This section contains array of function pointers. This array is iterated and each function is invoked by _init()->__do_global_ctors_aux() during program start. _init() is placed “.init” section so it will be called during program initialization. A function can be declared as constructor by using function <a href="http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Function-Attributes.html">attribute</a>.
“-ftest-coverage” creates a constructor per file. This constructor calls __gcov_init() and passes the gcov_info as argument.
<pre class="code">
samuel@ubuntu:~$objdump -t ./a.out | grep -i _GLOBAL__
0000000000400c7c l F .text 0000000000000010 _GLOBAL__sub_I_65535_0_main
</pre>
And disassembly of _GLOBAL__sub_I_65535_0_main
<pre class="code">
954 0000000000400c7c <_global__sub_i_65535_0_main>:
955 400c7c: 55 push %rbp
956 400c7d: 48 89 e5 mov %rsp,%rbp
957 400c80: bf 00 31 60 00 mov $0x603100,%edi
958 400c85: e8 a6 12 00 00 callq 401f30 <__gcov_init>
959 400c8a: 5d pop %rbp
960 400c8b: c3 retq
961 400c8c: 90 nop
962 400c8d: 90 nop
963 400c8e: 90 nop
964 400c8f: 90 nop
</__gcov_init></_global__sub_i_65535_0_main></pre>
gcov_init() implemented in libgcov stores all the gcov_info() passed in a linked list. This linked list is used to walk through all the gcov_info during program termination.
]]></content>
<link rel="replies" type="text/html" href="http://samueldotj.com/blog/gcov-internals-overview/#comments" thr:count="1" />
<link rel="replies" type="application/atom+xml" href="http://samueldotj.com/blog/gcov-internals-overview/feed/atom/" thr:count="1" />
<thr:total>1</thr:total>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[Plot your data using gnuplot]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/graph-your-data/" />
<id>http://samueldotj.com/blog/?p=7</id>
<updated>2013-08-26T17:35:10Z</updated>
<published>2012-02-28T04:27:00Z</published>
<category scheme="http://samueldotj.com/blog" term="C" /><category scheme="http://samueldotj.com/blog" term="Programming" /><category scheme="http://samueldotj.com/blog" term="Tools" />
<summary type="html"><![CDATA[System statistics are hard interpolate since usually they are collected in large quantities and sometimes represents large numbers. Recently I was doing a prototype and wanted to measure how much damage it would to the main project (in terms of performance); so used performance counter feature in the processor to measure some events(cache miss, memory […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/graph-your-data/"><![CDATA[System statistics are hard interpolate since usually they are collected in large quantities and sometimes represents large numbers. Recently I was doing a prototype and wanted to measure how much damage it would to the main project (in terms of performance); so used <a href="http://software.intel.com/en-us/articles/intel-performance-counter-monitor/">performance counter feature</a> in the processor to measure some events(cache miss, memory read etc) with and without my code change. But after looking at the numbers I realized it is difficult to analyze such a data. Because each number is 8 digit and I had 16 columns(16 cpu) and 100 rows of data(100 seconds of run). So I decided to use some graph so that it would be easy to understand the data.
Googled for a GNU graph tool and found <a href="http://gnuplot.info/">gnu plot</a> – this blog is to show how good it is and how easy it is to use. Consider using it if you have lot of numbers. For this post I took some sample data from my ubuntu machine while running <a href="http://weather.ou.edu/~apw/projects/stress/">stress </a>command. 
[codegroup] 
[shell tab=’output’] 
cat stat.txt 
procs ———–memory———- —swap– —–io—- -system– —-cpu—- 
r b swpd free buff cache si so bi bo in cs us sy id wa 
0 0 251124 1827388 4720 32704 6 34 19 38 42 74 1 0 98 1 
0 0 251124 1827388 4720 32708 0 0 0 0 104 71 0 0 100 0 
13 3 251108 1349912 4728 322540 4 0 4 20 683 1789 42 12 47 0 
11 3 251008 1382620 4728 322520 180 0 180 0 1604 1233 89 12 0 0 
11 3 251008 1432052 4728 322520 0 0 0 0 1361 1237 90 10 0 0 
11 3 251008 1298352 4728 322668 0 0 0 0 1392 1275 90 10 0 0 
2 3 251008 1512576 4728 323524 0 0 0 0 20077 14827 59 16 13 12 
0 0 251008 1826388 4728 32756 0 0 0 0 45069 25566 0 4 25 71 
0 0 251008 1826444 4728 32708 0 0 0 0 59 46 0 0 100 0 
… 
[/shell]
[shell tab=’stress’] 
stress –cpu 8 –io 4 –vm 2 –vm-bytes 128M –hdd 2 –timeout 200s 
[/shell]
[shell tab=’vmstat’] 
sudo vmstat -n 1 200 > stat.txt 
[/shell] 
[/codegroup]
The following example shows how to create line graph for us, sy columns in the above against time(seconds). 
<a href="http://samueldotj.com/blog/wp-content/uploads/2012/02/output.jpg"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2012/02/output-300x225.jpg" alt="output" width="300" height="225" class="aligncenter size-medium wp-image-71" srcset="http://samueldotj.com/blog/wp-content/uploads/2012/02/output-300x225.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2012/02/output.jpg 640w" sizes="(max-width: 300px) 100vw, 300px" /></a>
This graph might not be impressive because it deals with only numbers ranging from 0-100 and the numbers are very steady. Consider a range 0-99999999 and the numbers are fluctuating too much then it will be to graph. The above graph was created by running “gnuplot” with following commands 
[shell] 
set title ‘CPU usage’ 
#set terminal svg butt enhanced dynamic 
set terminal jpeg 
set output ‘output.jpg’ 
set xlabel ‘seconds’ 
#set logscale y 
set ylabel ‘cpu’ 
set key below 
plot \ 
“stat.txt” using :13 title ‘Application’ with lines lc rgb ‘blue’, \ 
“stat.txt” using :14 title ‘Kernel’ with lines lc rgb ‘green’ 
[/shell]
You can also intermix two or more data files. The following example shows how to graph two different samples collected during different time period. 
[shell] 
set title ‘CPU usage’ 
#set terminal svg butt enhanced dynamic 
set terminal jpeg 
set output ‘output.jpg’ 
set xlabel ‘seconds’ 
#set logscale y 
set ylabel ‘cpu’ 
set key below 
plot \ 
“stat.txt” using :13 title ‘Application’ with lines lc rgb ‘light-green’, \ 
“stat.txt” using :14 title ‘Kernel’ with lines lc rgb ‘light-red’, \ 
“stat1.txt” using :13 title ‘Application1’ with lines lc rgb ‘dark-green’, \ 
“stat1.txt” using :14 title ‘Kernel1’ with lines lc rgb ‘dark-red’ 
[/shell] 
The stat1.txt file is generated by running <a href="http://linux.about.com/library/cmd/blcmdl8_vmstat.htm">vmstat </a>while the system was stressed by the following command 
[shell]stress –cpu 4 –io 2 –vm 4 –vm-bytes 1M –hdd 2 –hdd-bytes 4096 –timeout 200s[/shell]
<a href="http://samueldotj.com/blog/wp-content/uploads/2012/02/output-1.jpg"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2012/02/output-1-300x225.jpg" alt="Output" width="300" height="225" class="aligncenter size-medium wp-image-70" srcset="http://samueldotj.com/blog/wp-content/uploads/2012/02/output-1-300x225.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2012/02/output-1.jpg 640w" sizes="(max-width: 300px) 100vw, 300px" /></a>
The nice thing about gnuplot is it will skip the row(line) in the data file if it cant recognize the columns. And also it supports svg and pdf outputs. See what all gnuplot can do at the official <a href="http://gnuplot.sourceforge.net/demo/">demo page</a>.
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[OpenOCD and NGX USB ARM JTAG]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/openocd-and-ngx-usb-arm-jtag/" />
<id>http://samueldotj.com/blog/?p=8</id>
<updated>2013-08-26T17:56:17Z</updated>
<published>2011-05-22T13:04:00Z</published>
<category scheme="http://samueldotj.com/blog" term="C" /><category scheme="http://samueldotj.com/blog" term="Compiler" /><category scheme="http://samueldotj.com/blog" term="Debugger" />
<summary type="html"><![CDATA[This post describes the steps needed to make NGX’s USB ARM JTAG to work with OpenOCD in windows 7. This JTAG is compatible with colink JTAG and works with IAR Workbench and Keil uVision. To use with these IDEs there is a well defined methods/plug-ins available in the product page and in internet. However to […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/openocd-and-ngx-usb-arm-jtag/"><![CDATA[<div id="attachment_75" style="width: 160px" class="wp-caption alignright"><a href="http://samueldotj.com/blog/wp-content/uploads/2011/05/usb_jtag1.jpg"><img loading="lazy" decoding="async" aria-describedby="caption-attachment-75" src="http://samueldotj.com/blog/wp-content/uploads/2011/05/usb_jtag1-150x150.jpg" alt="NGX’s USB ARM JTAG" width="150" height="150" class="size-thumbnail wp-image-75" /></a>NGX’s USB ARM JTAG</div>
This post describes the steps needed to make <a href="http://shop.ngxtechnologies.com/product_info.php?cPath=26&products_id=30">NGX’s USB ARM JTAG</a> to work with <a href="http://openocd.berlios.de/web/">OpenOCD </a>in windows 7. This <a href="http://en.wikipedia.org/wiki/Joint_Test_Action_Group">JTAG </a>is compatible with <a href="http://www.coocox.org/Colink.htm">colink </a>JTAG and works with<a href="http://www.iar.com/"> IAR Workbench</a> and <a href="http://www.keil.com/uvision/">Keil uVision</a>. To use with these IDEs there is a well defined methods/plug-ins available in the product page and in internet. However to use this JTAG with OpenOCD there is scarce resource in the internet.
OpenOCD can be used to low level debugging, source level debugging (through GDB) and can be used for flashing. OpenOCD exposes a command line interface which can be accessed through telnet. It also provides remote GDB server which also can be reached through TCP connection.
Steps needed for Windows:
<ol>
<li>Plug-In the JTAG to a available USB connector</li>
<li>Download <a href="http://sourceforge.net/projects/libusb-win32/files/">libusb-win32</a></li>
<li>Extract libusb-win32 to a folder and run “inf-wizard.exe”</li>
<li>Select “USB Serial Converter A” and install driver</li>
<li>Download and install <a href="http://www.freddiechopin.info/index.php/en/download/category/4-openocd">OpenOCD</a></li>
<li>Attach the JTAG probe to your target ARM board and poweron the target board</li>
<li>Create a openocd configurations file (see at the end)</li>
<li>Run openocd.exe –f</li>
<li>Run putty or telnet and connect to port localhost:4444</li>
</ol>
After this the target board will respond to JTAG commands which can be issued through the telnet session.
For GDB debugging, you need a cross compiled GDB(<a href="http://www.codesourcery.com/sgpp/lite/arm/portal/subscription?@template=lite">arm-none-eabi-gdb</a>). 
After launching arm-none-eabi-gdb.exe run target remote localhost:3333 to start remote debugging. 
You can execute low level JTAG commands from GDB by using monitor command.
Flashing can be done using the following commands: 
[shell] 
reset 
halt 
sleep 200 
wait_halt 
flash probe 0 
flash info 0 
flash write_image erase unlock 
sleep 200 
reset run 
[/shell]
OpenOCD configuration file: 
[shell] 
# openocd configurations 
telnet_port 4444
# gdb configuration 
gdb_port 3333
# cpu configuration 
source [find target/lpc1768.cfg]
# interface configuration 
interface ft2232 
ft2232_vid_pid 0x0403 0x6010 
ft2232_device_desc “NGX JTAG” 
ft2232_layout “oocdlink” 
ft2232_latency 2 
[/shell]
]]></content>
<link rel="replies" type="text/html" href="http://samueldotj.com/blog/openocd-and-ngx-usb-arm-jtag/#comments" thr:count="1" />
<link rel="replies" type="application/atom+xml" href="http://samueldotj.com/blog/openocd-and-ngx-usb-arm-jtag/feed/atom/" thr:count="1" />
<thr:total>1</thr:total>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[DIY – Wirless Router and NAS: Software Pieces]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/wirless-router-network-storage-and-media-server-software-pieces/" />
<id>http://samueldotj.com/blog/?p=9</id>
<updated>2013-08-27T01:22:45Z</updated>
<published>2011-03-12T16:43:00Z</published>
<category scheme="http://samueldotj.com/blog" term="Router NAS Linux" /><category scheme="http://samueldotj.com/blog" term="Softwares" />
<summary type="html"><![CDATA[This is the followup post of DIY – RCN. Here I document about the different software used to make my RCN. Operating System There are two open source choices BSD(FreeBSD) or Linux(ubuntu). After few days of analysis I decided to go with Linux – because in my work I use FreeBSD. In either case I […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/wirless-router-network-storage-and-media-server-software-pieces/"><![CDATA[This is the followup post of <a href="http://samueldotj.com/blog/?p=10">DIY – RCN</a>. Here I document about the different software used to make my RCN.
<h2>Operating System</h2>
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/03/linux-ubuntu2.gif"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/03/linux-ubuntu2.gif" alt="linux-ubuntu" width="48" height="48" class="alignright size-full wp-image-81" /></a> There are two open source choices <a href="http://www.freebsd.org/">BSD</a>(FreeBSD) or <a href="http://www.ubuntu.com/">Linux</a>(ubuntu). After few days of analysis I decided to go with Linux – because in my work I use FreeBSD. In either case I did not want to use <a href="http://freenas.org/">FreeNAS</a> or <a href="http://www.openfiler.com/">OpenFiler</a> or any other ready made distro. Since I am familiar with Ubuntu, I decided to use the <a href="http://www.ubuntu.com/business/server/overview">Ubuntu server</a> version.
<h3>File System</h3>
Wanted to use <a href="http://en.wikipedia.org/wiki/ZFS">ZFS </a>on my main storage disk but it is not available on Linux yet, so decided to go with <a href="http://en.wikipedia.org/wiki/XFS">XFS</a>. EXT3/4 on the boot disk because it is natively supported and no extra package needed. The boot media is 8GB flash disk.
<h2>Installation</h2>
Since there is no optical disk drive, installation should be through network or USB. Since most of the Linux distributions supports that I decided to use USB.
<ol>
<li>Download <a href="http://www.ubuntu.com/business/get-ubuntu/download">Ubuntu 10.10 server</a></li>
<li>Download <a href="http://www.pendrivelinux.com/universal-usb-installer-easy-as-1-2-3/">Universal USB installer</a></li>
<li>Create bootable install media using the installer</li>
<li>Boot the system with boot media</li>
</ol>
<h3>Partitions</h3>
Although no data is going to be stored in the boot media, it would be good to have separate partitions to store the config files and home directory. Otherwise re-installation would wipe out all the data.
I chose to create 5 partitions 
[shell] 
/ – EXT4 – 2GB 
/usr – EXT4 – 2GB 
/var – EXT4 – 2GB 
/home – EXT4 – 1GB 
swap – – 1GB 
[/shell]
<h2>Management</h2>
Since this device will run headless only way to communicate with the system is through network interface. Having SSH access is good but still having a web interface for common administration access is better. Few Linux applications are available for that my choice is <a href="http://www.webmin.com/">Webmin</a>. 
[shell] 
sudo vi /etc/apt/sources.list 
wget http://www.webmin.com/jcameron-key.asc 
sudo apt-key add jcameron-key.asc 
sudo apt-get update 
sudo apt-get install webmin 
[/shell] 
After this the machine can be controlled from local network – https://hostname:10000/
<h3>Shutdown</h3>
Shutting down the system should be easy. Since the storage is connected to the system it cant be power off directly. The file system data should be syncd first and using command line or web interface is not realistic. So programming the ATX power switch is the only way – acpid does that. 
[shell] 
sudo apt-get install acpid 
[/shell]
<h2>Storage</h2>
The goal was to create file based storage which is accessible from my home network. The <a href="http://en.wikipedia.org/wiki/Network-attached_storage">NAS server</a> should be big enough for at least next 2 years(1TB). It should be fast enough to view videos from it without flickering(64MB ondisk buffer). It should have hardware fault tolerance(<a href="http://en.wikipedia.org/wiki/RAID">RAID</a>).
Although few of my desktop boards had RAID option in the BIOS menu, I never used it and never explored it. I thought RAID chipsets in a motherboard is equivalent to RAID controllers/adapters. It was one of the decideding factor I favoured for Gigabyte(GA-D425TUD) motherboard with JMicron RAID chipset over Intel(D525MO) motherboard.
After configuring RAID in the BIOS and starting Linux I realized it is not true raid. Because Linux recognized as fakeraid. In simple terms fakeraid is a firmware based RAID. That is all the work is still to be done in software yielding no performance benefit. Advantage of fakeraid is multiple OS which runs on same box can utiltize the same RAID. Since my setup wont have multiboot option, I dont want the fakeraid so decided to go with pure software RAID 0. Here is the steps to create software raid 0.
<ol>
<li>Create software raid using multiple devices(md) interface.</li>
 [shell]mdadm –create –verbose /dev/md0 –level=1 –raid-devices=2 /dev/sda /dev/sdb[/shell]
<li>The above command will take some time (around 6 hours) because it needs to sync the contents of both disks. 
While it is doing that the status can be checked by using the following command.</li>
 [shell]cat /proc/mdstat[/shell]
<li>Then create a XFS file system on the md device</li>
 [shell]mkfs.xfs /dev/md0[/shell]
<li>Store the configuration</li>
 [shell]mdadm –detail –scan > /etc/mdadm/mdadm.conf[/shell]
<li>Create mount point and add the mount information in the /etc/fstab</li>
 [shell] 
mkdir /mnt/raid 
echo “/dev/md0 /mnt/raid xfs defaults 1 2” >> /etc/fstab 
[/shell]
</ol>
<h3>Windows File Sharing</h3>
After this /mnt/raid can be made accessible to remote machines through either NFS or through Windows File Sharing. For Windows File Sharing <a href="http://www.samba.org/">samba </a>service needed to installed. The following command installs samba server. 
[shell]sudo apt-get install samba[/shell]
After installing samba server it can be configured using webmin. Use webmin to configure samba “Servers”->”Samba File sharing”. Add the storage mount point here.
<h2>Router</h2>
The routing functionality is very simple – handle all 3 interfaces with some limitations. 
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/03/RCN.png"><img loading="lazy" decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/03/RCN-300x148.png" alt="RCN" width="300" height="148" class="alignright size-medium wp-image-85" srcset="http://samueldotj.com/blog/wp-content/uploads/2011/03/RCN-300x148.png 300w, http://samueldotj.com/blog/wp-content/uploads/2011/03/RCN.png 427w" sizes="(max-width: 300px) 100vw, 300px" /></a>
<ul>
<li>First interface eth0 is a Gigabit ethernet interface which is directly connected to the a desktop computer.</li>
<li>Second interface eth1 is a Fast ethernet interface which is directly connected to internet(connected to a ADSL modem).</li>
<li>Third interface is 802.11n wireless network.</li>
</ul>
<h3>Network and IP</h3>
All interfaces are in different networks. All interface should get static IPv4 address while booting up. This router should provide dynamic IP to the other machines.
Modify network interface and dhcp configurations 
[codegroup] 
[shell tab=”/etc/network/interface”] 
# This file describes the network interfaces available on your system 
# and how to activate them. For more information, see interfaces(5).
# The loopback network interface 
auto lo 
iface lo inet loopback
# The primary network interface 
auto eth0 
iface eth0 inet static 
address 192.168.1.2 
netmask 255.255.255.0 
gateway 192.168.100.2 
post-up iptables-restore < /etc/iptables.up.rules
up /etc/init.d/dhcp3-server start
#wireless network
auto wlan0
iface wlan0 inet static
address 192.168.2.1
netmask 255.255.255.0
gateway 192.168.100.2
up /etc/init.d/dhcp3-server start
#wan interface
auto eth1
iface eth1 inet static
address 192.168.100.2
netmask 255.255.255.0
gateway 192.168.100.1
[/shell]
[shell tab='/etc/dhcp3/dhcpd.conf']
subnet 192.168.1.0 netmask 255.255.255.0 {
range 192.168.1.100 192.168.1.200;
option domain-name-servers 208.67.222.222, 208.67.220.220;
option routers 192.168.1.2;
option broadcast-address 192.168.1.255;
default-lease-time 600;
max-lease-time 7200;
}
subnet 192.168.2.0 netmask 255.255.255.0 {
range 192.168.2.100 192.168.2.200;
option domain-name-servers 208.67.222.222, 208.67.220.220;
option routers 192.168.2.1;
option broadcast-address 192.168.2.255;
default-lease-time 600;
max-lease-time 7200;
}
[/shell]
[/codegroup]
Finally enable forwarding in Linux kernel by setting a system tunable.
[shell]echo 1 > /proc/sys/net/ipv4/ip_forward[/shell]
To set it during boot modify /etc/sysctl.conf
<h3><a href="http://en.wikipedia.org/wiki/Network_address_translation">NAT – Network Address Translation</a></h3>
NAT is required on eth1 to translate addresses on any outgoing packets and incoming packets. For the iptable rules should be set correctly, the following script does that. 
[shell] 
INTIF=”eth0″ 
EXTIF=”eth1″
#set default polices and flush 
iptables -P INPUT ACCEPT 
iptables -F INPUT 
iptables -P OUTPUT ACCEPT 
iptables -F OUTPUT 
iptables -P FORWARD DROP 
iptables -F FORWARD 
#setup NAT 
iptables -t nat -F 
iptables -t nat -A POSTROUTING -o $EXTIF -j MASQUERADE
iptables -A FORWARD -i $EXTIF -o $INTIF -m state –state ESTABLISHED,RELATED -j ACCEPT 
iptables -A FORWARD -i $INTIF -o $EXTIF -j ACCEPT
INTIF1=”wlan0″ 
iptables -A FORWARD -i $EXTIF -o $INTIF1 -m state –state ESTABLISHED,RELATED -j ACCEPT 
iptables -A FORWARD -i $INTIF1 -o $EXTIF -j ACCEPT
iptables -A FORWARD -i $INTIF -o $INTIF1 -j ACCEPT 
iptables -A FORWARD -i $INTIF1 -o $INTIF -j ACCEPT
#unblock certain services 
#webmin 
iptables -A INPUT -p tcp -m tcp –dport 10000 -j ACCEPT 
[/shell]
<h3>Wireless</h3>
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/03/wifi.jpg"><img decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/03/wifi.jpg" alt="wifi" width="125" class="alignright size-medium wp-image-82" /></a>Now it is time to setup the wireless interface. Assuming the wireless are drivers are present in the kernel. 
The other tool required is hostapd. hostapd implements IEEE 802.11 access point management. 
hostapd configuration 
[shell] 
interface=wlan0 
driver=nl80211
ctrl_interface=/var/run/hostapd 
ctrl_interface_group=0
ssid=rcnap 
hw_mode=g 
channel=11
ieee80211n=1 
#ht_capab=[HT40-][SHORT-GI-40]
wpa_pairwise=TKIP CCMP 
wpa=1 
[/shell]
]]></content>
</entry>
<entry>
<author>
<name>samueldotj</name>
</author>
<title type="html"><![CDATA[DIY – Wirless Router and NAS: Hardware bits]]></title>
<link rel="alternate" type="text/html" href="http://samueldotj.com/blog/how-to-create-your-own-wireless-router-network-storage-server-and-media-server/" />
<id>http://samueldotj.com/blog/?p=10</id>
<updated>2013-08-26T19:19:36Z</updated>
<published>2011-02-14T16:20:00Z</published>
<category scheme="http://samueldotj.com/blog" term="Router NAS Linux" />
<summary type="html"><![CDATA[I have replaced my Buffalo WRT-G54 wireless router with my own custom built router. This blog explains the details involved that process. I call this device as RCN (Router cum NAS). Hardware I began my hardware hunt 45 days back – it was difficult because of my requirements and availability in Indian Market. Here is […]]]></summary>
<content type="html" xml:base="http://samueldotj.com/blog/how-to-create-your-own-wireless-router-network-storage-server-and-media-server/"><![CDATA[I have replaced my Buffalo WRT-G54 wireless router with my own custom built router. This blog explains the details involved that process. I call this device as RCN (Router cum NAS).
<h2>Hardware</h2>
I began my hardware hunt 45 days back – it was difficult because of my requirements and availability in Indian Market.
Here is the initial requirement list I had(strike-through indicates I gave up that requirement because the items are too costly or not available in India):
<ul>
<li>Total board TDP should be less than 40 watts</li>
<li><s>Passively cooled</s></li>
<li>Mini-ITX form factor</li>
<li>Onboard RAID</li>
<li>DDR3 support</li>
<li><s>Dual core</s></li>
<li>Hardware should be available in India</li>
</ul>
Here is the final products I purchased:
<ul>
<li><a href="http://www.gigabyte.com/products/product-page.aspx?pid=3550#ov">Gigabyte GA-D425TUD</a></li>
<li><a href="http://iball.co.in/Product.aspx?c=5">iBall Baby 306</a> Cabinet</li>
<li>DDR-3 2GB RAM</li>
<li>2 x 1TB Western Digital <a href="http://www.wdc.com/en/products/products.aspx?id=120">WD10EARS</a> SATA</li>
<li>USB to Ethernet</li>
<li>USB Flash Drive</li>
<li>PCI Wifi Adapter <a href="http://www.dlink.com/products/?pid=531">DLink 552 Xtreme N</a></li>
</ul>
Here is some pictures of my RCN
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-012.jpg"><img decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-012-300x200.jpg" alt="RCN 012" width="150" class="alignright size-medium wp-image-92" srcset="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-012-300x200.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-012-1024x682.jpg 1024w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-012.jpg 1600w" sizes="(max-width: 300px) 100vw, 300px" /></a>
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-0061.jpg"><img decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-0061-300x200.jpg" alt="RCN 006" width="150" class="alignright size-medium wp-image-94" srcset="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-0061-300x200.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-0061-1024x682.jpg 1024w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-0061.jpg 1600w" sizes="(max-width: 300px) 100vw, 300px" /></a>
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-013.jpg"><img decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-013-300x200.jpg" alt="RCN 013" width="150" class="alignright size-medium wp-image-93" srcset="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-013-300x200.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-013-1024x682.jpg 1024w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-013.jpg 1600w" sizes="(max-width: 300px) 100vw, 300px" /></a>
<a href="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-010.jpg"><img decoding="async" src="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-010-300x200.jpg" alt="RCN 010" width="150" class="alignright size-medium wp-image-91" srcset="http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-010-300x200.jpg 300w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-010-1024x682.jpg 1024w, http://samueldotj.com/blog/wp-content/uploads/2011/02/RCN-010.jpg 1600w" sizes="(max-width: 300px) 100vw, 300px" /></a>
Interesting fact about <a href="http://www.wdc.com/en/products/products.aspx?id=120">WD10EARS</a> is it use 4KB sectors instead of the conventional 512byte sectors. Since this is a breakthrough software support is not much there. Looks like these drives perform poor if not partitioned properly – Since my requirement demands creating single partition, I purchased this drive and it performs well.
]]></content>
<link rel="replies" type="text/html" href="http://samueldotj.com/blog/how-to-create-your-own-wireless-router-network-storage-server-and-media-server/#comments" thr:count="1" />
<link rel="replies" type="application/atom+xml" href="http://samueldotj.com/blog/how-to-create-your-own-wireless-router-network-storage-server-and-media-server/feed/atom/" thr:count="1" />
<thr:total>1</thr:total>
</entry>
</feed>

If you would like to create a banner that links to this page (i.e. this validation result), do the following:

Download the "valid Atom 1.0" banner.
Upload the image to your own server. (This step is important. Please do not link directly to the image on this server.)
Add this HTML to your page (change the image src attribute if necessary):

<a href="http://www.feedvalidator.org/check.cgi?url=http%3A//samueldotj.com/blog/%3Ffeed%3Datom"><img src="valid-atom.png" alt="[Valid Atom 1.0]" title="Validate my Atom 1.0 feed" /></a>

If you would like to create a text link instead, here is the URL you can use:

http://www.feedvalidator.org/check.cgi?url=http%3A//samueldotj.com/blog/%3Ffeed%3Datom

Home · About · News · Docs · Terms