Category Archives: Programming

Python Notes-2

This is continuation from Python Notes-1. We were learning about python list
li = []
I really like the way python never need the variable to be declared. It is automatically assigned the data type based on it’s last initialization. e.g.


a = 9
a = 'q'


>>> a = 9
>>> type(a)

>>> a = 'q'
>>> type(a)

>>> a = []
>>> type(a)

As we know from last post that python string are immutable similarly we have another data structure in python called tuple which is similar to list but it is immutable.

var = ()
var = ('abc',3,4.8)

You can’t do var[0] = 3 also if there is only one element in the tuple it doesn’t make sense to write it like var = (2) or var = (x) as this will just mean var = 2 or var = x. So you have to do it like var = (2,) or var = (x,). One item tuple will need a trailing comma.

len() will give you length of a variable like
var = "12345" then len(var) will be 5.
Similarly var = [1,2,3,4,5] len(var)

Negative index This is very handy in accessing elements from last so you can say:


var = [1,2,3,4,5]
var[-1]
This will give you the last element of the list. This can be applied similarly to list or tuple
-2 will refer to second last element.

Slicing


var = ['apple', 'ball', 'cat', 'dog']
>>> spam[:2]
['apple', 'ball']
>>> spam[1:]
['ball', 'cat', 'dog']

Reading from standard input


var = input()

var will be of str type. Also note that Python doesn’t have char data type.

var = int(input())
will try to convert what is read to int.

One important list method is append()
used extensibly in a loop to keep on adding things.

insert() method to insert at a particular index first argument is index second argument is what to insert. insert(indx,val)


li = [1, 2]
>>> li.append(4)
>>> li.insert(2,3)
>>> li
[1, 2, 3, 4]
>>> li.insert(2,3)
>>> li
[1, 2, 3, 3, 4]
>>> del(li[2])
>>> li
[1, 2, 3, 4]

A sample code

To be continued …

Advertisements

Python Notes – 1

I think python is best for any personal use (small scale development) prototyping ideas etc.

Some examples:
Like say I want to parse a document for some specific keywords and format the extracted data.
I want to get update when something on some website changes.
I want to teach a lesson to a spammer by sending him lots and lots of email.
For investing you want to make sense out of some stocks historic data. Using numpy and pandas. Using pandas reading data in meaningful way from a web resource is as easy as reading it from local file.
You want to download all the news paper resources (having a particular date format) from an internet location

All above are my actual use cases to give you an idea.Apart from this I think Python is made for interviews it is very simple to write algorithms or create a data structure in Python. (I guess)

That said now let us get to work and learn some python you will find many online resources really good resources or you can join open/free courses from coursera or similar sites. If you don’t want all this you can right away jump into coding and google(basically stack overflow) your requirements as it arises. (given that you have prior experience with programming and at least one language). This may be problamatic as it will not teach you to code in the Pythonic way. But you can cover that later by browsing some existing good resources/libraries.

Lots of talking now let us get back to work the really boring stuff in language learning syntax.

Note: The notes are all personal it is not meant to cover everything in the language. I am biased towards whatever interested me more or whatever was new for me.

** exponent
Example: 2**3 = 8 = 2 ^ 3

// Integer division/floored quotient

5//2 = 2 % gives you remainder as usual

List in python are object same as string although string are immutable similar to java string.

I don’t know why I assumed that python list should be like C++ STL vector. This was a shock to me when I got to know that python list are object just like any array in Java or C++. So if you pass it in a function which is modifying it it will be modified in caller also.
I was thinking may be in Python as long as possible things will be copied and passed around.

To be continued…

C++ STL std::array

A hybrid between c array and cpp vector but with lot of difference. Size has to be known at compile time. It can’t be dynamic.

Initialized as


std::array myarray;

5 is the size of the array must be known at compile time. You can access elements by [] (array) operator but this will not give in size check. For size check use at operator.


myarray.at(i)

myarray.size()

sort(myarray.begin(),myarray.end(), comparator)

Prim’s MST (Minimum Spanning Tree)

Given a graph with N nodes and M edges (Undirected) with positive weights. Find the minimum spanning tree. A tree with minimum overall weight edge. This is cover all nodes of the original graph if possible. You will be given a starting point S. Just in case the graph is not connected. Then you can find the MST which contains S.

 

Input Format

First line has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.

The next lines each consist of three space separated integers , first two integers are the two nodes between which the  edge exists, last/third integer is the weight of the edge.

The last line has an integer , denoting the starting node.

Nodes are numbered from 1 to N.

There can be multiple edges between same pair of nodes. Consider them as multiple edges.

 

Sample input:

3 3
1 2 2
1 3 3
3 2 6
1

Sample Output

5

 

Solution:

</pre>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge{
int begin;
int end;
int weight;
};
//minHeap
bool comp(const edge& a, const edge& b){
return (a.weight > b.weight);
}

void print(edge e){
cout<<e.begin<<" -> "<<e.end<<" w: "<<e.weight<<endl;
}
void prims(vector <vector <edge> > &adj, int start, int V){
vector <edge> minHeap;
int result = 0;
for(int i = 0; i < adj[start].size(); i++){
minHeap.push_back(adj[start][i]);
//print(adj[start][i]);
}
make_heap (minHeap.begin(),minHeap.end(), comp);
vector <bool> visited(V);
visited[start] = true;
while(!minHeap.empty()){
edge e = minHeap.front();
//cout<<"popped ";
//print(e);
pop_heap(minHeap.begin(), minHeap.end(),comp);
minHeap.pop_back();
if(!visited[e.end]){
visited[e.end] = true;
result += e.weight;
//cout<<"res: "<<result<<endl;
for(int i = 0; i < adj[e.end].size(); i++){
minHeap.push_back(adj[e.end][i]); push_heap(minHeap.begin(), minHeap.end(), comp);
//cout<<"push ";
//print(adj[e.end][i]);
}
}
}
cout<<result<<endl;
}

int main() {
int V, E, S;
cin>>V;
cin>>E;
vector <vector <edge> > adj(V);
for(int i = 0; i < E; i++){
int start, end, weight;
cin>>start;
cin>>end;
cin>>weight;
start--;end--;
edge e1;
e1.end = end;
e1.weight = weight;
e1.begin = start;
adj[start].push_back(e1);
edge e2;
e2.end = start;
e2.weight = weight;
e2.begin = end;
adj[end].push_back(e2);
}
cin>>S;
S--;
prims(adj,S, V);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}

Max Sum

Given an array of positive numbers, find the maximum sum of a sub-sequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the size of array.
The second line of each test case contains N input C[i].

Output:

Print the maximum sum of a sub-sequence.

 

C++ Solution


#include <iostream>
#include <vector>

using namespace std;

/*
T denotes maxsum then
T(N) = max(A[N-1] + T(N-2), T(N-1))
*/
void printMaxSum(vector <int> inp)
{
int size = inp.size();
vector <int> maxSum;
if(size <= 0)
return;
else
{
if(size == 1)
{
cout<<inp[0]<<endl;
return;
}
else
{
maxSum.push_back(inp[0]);
maxSum.push_back(max(inp[0],inp[1]));
}
}
for(int i = 2; i < size; i++)
{
int included = inp[i] + maxSum[i - 2];
int excluded = maxSum[i-1];
maxSum.push_back(max(included,excluded));
}
cout<< maxSum[size-1]<<endl;
}

int main() {
int T = 0;
//read number of test cases
cin>>T;
vector < vector <int> > allInputs;
for (int i = 0; i < T; i++)
{
int N = 0;
cin>>N;
//read all N inputs in a vector
vector <int> arr;
for(int j = 0; j < N; j++)
{
int inp = 0;
cin>>inp;
arr.push_back(inp);
}
allInputs.push_back(arr);
}

for(int i = 0; i < T; i++)
{
printMaxSum(allInputs[i]);
}

return 0;
}

USB data Sniffing and recreating similar behaviour

Sniff.. Sniff…

Recently I had to work on a USB camera device for Linux. The vendor has just given the example code for Windows. That example code also uses some pre-compiled library and dll file. So there is no way to know what exactly is happening when the software is run and device is controlled via the software. Basically I have to make filter switcher of the camera work in Linux. For windows vendor has provided with one filter switching application.

Usblyzer ( http://www.usblyzer.com/ ) is a great tool for sniffing USB traffic. It gives you almost everything required to re-create the scenario. I used this to see the USB packets and then used libusb for windows to re-create the scenario.

libusb: A Great Open source usb library

Making windows work with libusb:

Download most recent version of libusb. I used :

http://kaz.dl.sourceforge.net/project/libusb-win32/libusb-win32-releases/1.2.6.0/libusb-win32-bin-1.2.6.0.zip

go to bin folder and run the install-filter exe. Now you need to copy the dll and sys file. I did below for my PC:
ALL ARCHITECTURES:
x86\libusb0_x86.dll: x86 32-bit library. Must be renamed to libusb0.dll
On 32 bit, Installs to Windows\system32\libusb0.dll.

X86 ONLY ARCHITECTURES:
x86\libusb0.sys: x86 32-bit driver.
Installs to Windows\system32\drivers\libusb0.sys

After above steps you will be able to able to see your device info when you run testlibusb-win.exe from bin folder.

Get to work

Now create an empty Visual studio project.

Add proper libusb.lib in Linker => Input additional dependency. For my PC it was in lib/msvc/libusb.lib.

Include lusb0_usb.h in your main file.

Now you can write code to get device handle and send data. I am pasting my code for reference:

#include <stdio.h>
#include "lusb0_usb.h"
#include <iostream>
#include <windows.h>

using namespace std;

int main(int argc, char** argv)
{
usb_dev_handle *my_dev_hndl = NULL; /* the device handle */
struct usb_device *my_dev;

struct usb_bus *busses;

void usb_init(void);
usb_find_busses(); /* find all busses */
usb_find_devices(); /* find all connected devices */
busses = usb_get_busses();
struct usb_bus *bus;

/* ... */

for (bus = busses; bus; bus = bus->next)

{
struct usb_device *dev;

for (dev = bus->devices; dev; dev = dev->next)

{
/* Check if this device is a printer */
if (dev->descriptor.bDeviceClass == 239) {//you can find this in info of testlibusb
/* Open the device, claim the interface and do your processing */
printf("I am so happy \n");
my_dev = dev;
printf("%d\n",dev->descriptor.bDeviceClass);
cout<<"Number of possible configurations: "<descriptor.bnumconfigurations<<" "<<<span="" class="hiddenSpellError" pre="">endl;
cout<<"VendorID: "
cout<<"ProductID: "
my_dev_hndl = usb_open(dev);
/* only one configuration: #1 */
int ret = usb_set_configuration(my_dev_hndl, 1);
if (ret < 0)
{
printf("usb_set_configuration failed ret code: %d.\n", ret);
printf("%s\n", usb_strerror());
}

/* configuration #1, interface #0 */
ret = usb_claim_interface(my_dev_hndl, 0);
if (ret < 0)
{
printf("usb_claim_interface failed ret code: %d\n", ret);
printf("%s\n", usb_strerror());
//usb_close(my_dev_hndl);
}
}
char bmRequestType= 0x21;

unsigned char bRequest = 0x01;
unsigned short wValue = 0x400;
unsigned short wIndex = 0x400;
unsigned short wLength = 4;
unsigned int timeout = 1000;

char data_rec[2] = { 0x04, 0x00 };//20 32 B0 22
usb_control_msg(my_dev_hndl, 0xA1, 0x85, wValue, wIndex, data_rec, 2, timeout);

char data_init[4] = { 0x00, 0x00, 0x00, 0x00 };//20 32 B0 22
usb_control_msg(my_dev_hndl, bmRequestType, bRequest, wValue, wIndex, data_init,  wLength, timeout);

usb_control_msg(my_dev_hndl, 0xA1, 0x85, wValue, wIndex, data_rec, 2, timeout);

usb_control_msg(my_dev_hndl, 0xA1, 0x85, wValue, wIndex, data_rec, 2, timeout);

char data_init1[4] = { 0x00, 0x00, 0x00, 0xAA };//20 32 B0 22
usb_control_msg(my_dev_hndl, 0xA1, 0x81, wValue, wIndex, data_init1, wLength, timeout);
Sleep( 3 );
}
}
}

if (dev->descriptor.bDeviceClass == 239) {//you can find this in info of testlibusb

What I noticed here is when you are recreating the scenario you have to be careful about timing also otherwise it may result in “Bulk or Interrupt Transfer failure”

To get the info about usb_control_msg parameters you can check USBLYZER output. More info is displayed at bottom in summary and Analysis section.

Offset Field Size Value Description
0 bmRequestType 1 40h
4..0: Recipient ...00000 Device
6..5: Type .10..... Vendor
7: Direction 0....... Host-to-Device
1 bRequest 1 01h
2 wValue 2 0400h
4 wIndex 2 0400h
6 wLength 2 0004h

Now I recreated the same message sequence passing in Linux using libusb. I was able to achieve the same result on Linux without any help from device vendor. 🙂

In linux I faced the issue where device was always busy error code -6. This can be resolved by

libusb_detach_kernel_driver(h, 0);

h is device handle 0 is interface.

The sequence is same here also first list the device and find your device of interest. After this open your device and get dev handle detach the device to make sure no one else is using it. cal set_configuration and claim_interface. Prepare required data and send.

 

For debugging in Linux you can use usbmon. It comes with linux so nothing is required. Commands to see usbmon output:

sudo mount -t debugfs none_debugs /sys/kernel/debug

sudo modprobe usbmon

sudo cat /sys/kernel/debug/usb/devices

lsusb

ls /sys/kernel/debug/usb/usbmon

sudo cat /sys/kernel/debug/usb/usbmon/2u > ~/2u.mon.out

After above command see the output in file 2u.mon.out

2u is my device you can see output of all usb with 0u otherwise you need to search for your device bus with lsusb and sudo cat /sys/kernel/debug/usb/devices commands.

Windows Programming Multi language

Now a days I am doing some windows application development and I am loving it :).

I was not such a big fan of windows ever. I can understand the reasons for most of the issues which make windows not so great. Like they have to support so many verities of hardware so many versions and so many applications and all.

Anyhow I noticed that windows has very user-friendly development environment. There is less open source projects and less help for obvious reasons. This is kind of bottleneck but when I learned about dllimport I was like… ahhh great now I can do whatever I want. Developing GUI and simple stuff in C# and then using dllexport for existing libraries by just writing a wrapper file around the library. From there onward I have used it so much in all kind of development.

To explain usefulness of  dllexport I will use an example where I have to do some Video encoding and streaming. You already have great open source project for that. I want to integrate this with my C# application. For X264 encoding for sending data from network programming in C++. Used libavcodec libavformat to convert between formats muxing video data.

C/C++ Part

I will explain with one simple example how to use dllexport to create cool windows project here.

Let us first take a simple example, say I want to use a C function defined below:

int func(int arg)
{
  int result = 0;
//some kind of processing
  //may call other defined C functions
  return result;
}

Say above function call along with all useful stuff is in some file example.c. It may be in multiple files also. We just want to use the func call in C#. We will redefine the function as below:

__declspec(dllexport) int  __cdecl func(int arg)
{
//..
//same stuff
 

To be user-friendly we can define two macros as below:

#define DLLEXPORT __declspec(dllexport)
#define CDECL __cdecl

Now our function will look pretty good:

DLLEXPORT int  CDECL func(int arg)
{
  //..
  //same stuff

by //same stuff I mean the function body of func
Now we compile all c code as we were doing earlier but this time we compile it to create a dll library. GCC provides command to do so:
First compile all the files including example.c file and get the object files

gcc -c -o example.o example.c

gcc <strong>-shared</strong> -o library.dll example.o other_files.o other_libraries.a
 

other_files.o other_libraries.a are optional only required if your C project is big and uses multiple files and libraries. We will see it in next example when using X264 for encoding from C# project.

C# Part

We are almost done Now we just need to write our C# code and wherever in C# we want to use the function(func) from example.c we first declare the function as below:

[DllImport("library.dll")]
static extern int func(int arg);

Now we are free to use this function in our C# code just like any other function.
func(3);
That’s all so simple.
Now let us check one example where we will use libx264. We can do the same for ffmpeg by creating the ffmpeg dll. Sometime when there is problem of passing one struct variable from one C function to another C function. Say you want to use ffmpeg from one side while you also want to use X264. Since in C# we can’t just define these struct we will use IntPtr whenever there is any such requirement. This generally comes very handy in some cases.
I guess I will do another post for this as this post is already long.
Scratch Pad:

gcc -shared -o libmpegts.dll main.o libmpegts.a
gcc -I. -c -o tsmuxer.o tsmuxer.c

gcc -shared -o tsmuxer.dll tsmuxer.o -L. -lavformat -lavcodec -lavutil -lWs2
_32 -liconv

Scratchpad:

[DllImport("Kernel32.dll")]
static extern Boolean Beep(UInt32 frequency, UInt32 duration);

[DllImport("libx264", CallingConvention = CallingConvention.Cdecl)]
private static extern IntPtr initializePicOut();

DLLEXPORT x264_picture_t* CDECL initializePicOut()
{
}

DLLEXPORT x264_t* CDECL setX264Params(int width, int height, int FPS)
{
printf("setX264Params width: %d, height: %%d FPS: %d.\n", width, height, FPS);
x264_param_t param;
int res = 0;
res = x264_param_default_preset(¶m, "veryfast", "zerolatency");
if(res != 0) {
printf("error: cannot set the default pre-set on x264.\n");
return -1;
}
param.i_threads = 1;
param.i_width = width;
param.i_height = height;
param.i_fps_num = FPS;
param.i_fps_den = 1;
// Intra refres:
param.i_keyint_max = FPS;
param.b_intra_refresh = 1;
//Rate control:
param.rc.i_rc_method = X264_RC_CRF;
param.rc.f_rf_constant = FPS-5;
param.rc.f_rf_constant_max = FPS + 5;
//For streaming:
param.b_repeat_headers = 1;
param.b_annexb = 1;
res = x264_param_apply_profile(¶m, "baseline");
if(res != 0) {
printf("error: cannot set the baseline profile on x264.\n");
return -2;
}
}