| How to fast multiply a number by 7? | ||
| Try This is same as |
--
Monday, April 26, 2010
How to fast multiply a number by 7
--
Sunday, April 25, 2010
Unix programming Faq
Unix Programming FAQ (v1.37)
| There are reader questions on this topic! Help others by sharing your knowledge |
From: Andrew Gierth <andrew@erlenstar.demon.co.uk>
Newsgroups: comp.unix.programmer
Subject: Unix Programming FAQ (v1.37)
Date: 23 Oct 2003 19:40:02 +0100
Message-ID: <auto-cup-faq-000136-20031023194001@erlenstar.demon.co.uk>
Summary: This posting contains answers to frequently-asked questions regarding
programming in the Unix environment.
Keywords: unix faq
X-Post-Filter: postfilter v0.6 alpha
Archive-Name: unix-faq/programmer/faq
Comp-unix-programmer-Archive-Name: faq
URL: http://www.erlenstar.demon.co.uk/unix/faq_toc.html
URL: http://www.whitefang.com/unix/faq_toc.html
Posting-Frequency: every 2 weeks
Copyright: Collection Copyright (C) 1997-2000 Andrew Gierth.
Last-Modified: 2000/09/01 06:34:57
Version: 1.37
==============================================================================
About this FAQ
**************
$Id: rawfaq.texi,v 1.37 2000/09/01 06:34:57 andrew Exp $
This FAQ was originally begun by Patrick Horgan in May 1996; I took it over
after it had been lying idle for several months. I've reorganised it a bit
and added some stuff; I still regard it as `under development'.
Comments, suggestions, additions, corrections etc. should be sent to the
maintainer at: <andrew@erlenstar.demon.co.uk>.
A hypertext version of this document is available on the WWW. The home site
is located at `http://www.erlenstar.demon.co.uk/unix/faq_toc.html'. A US
mirror site is available at `http://www.whitefang.com/unix/faq_toc.html'.
This document is available by FTP from the news.answers archives at
rtfm.mit.edu and its many mirror sites worldwide. The official archive name
is `unix-faq/programmer/faq'. Sites which also archive *.answers posts by
group should also carry the file under the `comp.unix.programmer' directory.
Other sources of information are not listed here. You can find pointers to
other FAQs, books, source code etc. in the regular [READ ME FIRST] posting
that should appear weekly in comp.unix.programmer. Administrivia regarding
newsgroup conduct, etc., are also found there; I want to reserve this
document specifically for technical Q's and A's.
All contributions have been edited by the maintainer, therefore any errors
or omissions are my responsibility rather than that of the contributor.
This FAQ is now maintained as Texinfo source; I'm generating a raw text
version for Usenet using the `makeinfo' program, and an HTML version using
`texi2html'.
Copyright (C) 1997, 1998, 1999, 2000 Andrew Gierth. This document may be
distributed freely on Usenet or by email; it may be archived on FTP or WWW
sites that mirror the news.answers archives, provided that all reasonable
efforts are made to ensure that the archive is kept up-to-date. (This
permission may be withdrawn on an individual basis.) It may not be
published in any other form, whether in print, on the WWW, on CD-ROM, or in
any other medium, without the express permission of the maintainer.
List of contributors in no particular order:
Andrew Gierth <andrew@erlenstar.demon.co.uk>
Patrick J. Horgan withheld
Stephen Baynes <stephen.baynes@soton.sc.philips.com>
James Raynard withheld
Michael F. Quigley withheld
Ken Pizzini withheld
Thamer Al-Herbish withheld
Nick Kew <nick.kew@pobox.com>
Dan Abarbanel withheld
Billy Chambless <billy@cast.msstate.edu>
Walter Briscoe <walter@wbriscoe.demon.co.uk>
Jim Buchanan <jbuchana@buchanan1.net>
Dave Plonka <plonka@doit.wisc.edu>
Daniel Stenberg withheld
Ralph Corderoy <ralph@inputplus.demon.co.uk>
Stuart Kemp withheld
Sergei Chernev <ser@nsu.ru>
Bjorn Reese withheld
Joe Halpin <jhalpin@nortel.ca>
Aaron Crane <aaronc@pobox.com>
Geoff Clare <gwc@root.co.uk>
List of Questions
*****************
1. Process Control
1.1 Creating new processes: fork()
1.1.1 What does fork() do?
1.1.2 What's the difference between fork() and vfork()?
1.1.3 Why use _exit rather than exit in the child branch of a fork?
1.2 Environment variables
1.2.1 How can I get/set an environment variable from a program?
1.2.2 How can I read the whole environment?
1.3 How can I sleep for less than a second?
1.4 How can I get a finer-grained version of alarm()?
1.5 How can a parent and child process communicate?
1.6 How do I get rid of zombie processes?
1.6.1 What is a zombie?
1.6.2 How do I prevent them from occuring?
1.7 How do I get my program to act like a daemon?
1.8 How can I look at process in the system like ps does?
1.9 Given a pid, how can I tell if it's a running program?
1.10 What's the return value of system/pclose/waitpid?
1.11 How do I find out about a process' memory usage?
1.12 Why do processes never decrease in size?
1.13 How do I change the name of my program (as seen by `ps')?
1.14 How can I find a process' executable file?
1.14.1 So where do I put my configuration files then?
1.15 Why doesn't my process get SIGHUP when its parent dies?
1.16 How can I kill all descendents of a process?
2. General File handling (including pipes and sockets)
2.1 How to manage multiple connections?
2.1.1 How do I use select()?
2.1.2 How do I use poll()?
2.1.3 Can I use SysV IPC at the same time as select or poll?
2.2 How can I tell when the other end of a connection shuts down?
2.3 Best way to read directories?
2.4 How can I find out if someone else has a file open?
2.5 How do I `lock' a file?
2.6 How do I find out if a file has been updated by another process?
2.7 How does the `du' utility work?
2.8 How do I find the size of a file?
2.9 How do I expand `~' in a filename like the shell does?
2.10 What can I do with named pipes (FIFOs)?
2.10.1 What is a named pipe?
2.10.2 How do I create a named pipe?
2.10.3 How do I use a named pipe?
2.10.4 Can I use a named pipe across NFS?
2.10.5 Can multiple processes write to the pipe simultaneously?
2.10.6 Using named pipes in applications
3. Terminal I/O
3.1 How can I make my program not echo input?
3.2 How can I read single characters from the terminal?
3.3 How can I check and see if a key was pressed?
3.4 How can I move the cursor around the screen?
3.5 What are pttys?
3.6 How to handle a serial port or modem?
3.6.1 Serial device names and types
3.6.2 Setting up termios flags
3.6.2.1 c_iflag
3.6.2.2 c_oflag
3.6.2.3 c_cflag
3.6.2.4 c_lflag
3.6.2.5 c_cc
4. System Information
4.1 How can I tell how much memory my system has?
4.2 How do I check a user's password?
4.2.1 How do I get a user's password?
4.2.2 How do I get shadow passwords by uid?
4.2.3 How do I verify a user's password?
5. Miscellaneous programming
5.1 How do I compare strings using wildcards?
5.1.1 How do I compare strings using filename patterns?
5.1.2 How do I compare strings using regular expressions?
5.2 What's the best way to send mail from a program?
5.2.1 The simple method: /bin/mail
5.2.2 Invoking the MTA directly: /usr/lib/sendmail
5.2.2.1 Supplying the envelope explicitly
5.2.2.2 Allowing sendmail to deduce the recipients
6. Use of tools
6.1 How can I debug the children after a fork?
6.2 How to build library from other libraries?
6.3 How to create shared libraries / dlls?
6.4 Can I replace objects in a shared library?
6.5 How can I generate a stack dump from within a running program?
1. Process Control
******************
1.1 Creating new processes: fork()
==================================
1.1.1 What does fork() do?
--------------------------
#include <sys/types.h>
#include <unistd.h>
pid_t fork(void);
The `fork()' function is used to create a new process from an existing
process. The new process is called the child process, and the existing
process is called the parent. You can tell which is which by checking the
return value from `fork()'. The parent gets the child's pid returned to
him, but the child gets 0 returned to him. Thus this simple code
illustrate's the basics of it.
pid_t pid;
switch (pid = fork())
{
case -1:
/* Here pid is -1, the fork failed */
/* Some possible reasons are that you're */
/* out of process slots or virtual memory */
perror("The fork failed!");
break;
case 0:
/* pid of zero is the child */
/* Here we're the child...what should we do? */
/* ... */
/* but after doing it, we should do something like: */
_exit(0);
default:
/* pid greater than zero is parent getting the child's pid */
printf("Child's pid is %d\n",pid);
}
Of course, one can use `if()... else...' instead of `switch()', but the
above form is a useful idiom.
Of help when doing this is knowing just what is and is not inherited by the
child. This list can vary depending on Unix implementation, so take it
with a grain of salt. Note that the child gets *copies* of these things,
not the real thing.
Inherited by the child from the parent:
* process credentials (real/effective/saved UIDs and GIDs)
* environment
* stack
* memory
* open file descriptors (note that the underlying file positions are
shared between the parent and child, which can be confusing)
* close-on-exec flags
* signal handling settings
* nice value
* scheduler class
* process group ID
* session ID
* current working directory
* root directory
* file mode creation mask (umask)
* resource limits
* controlling terminal
Unique to the child:
* process ID
* different parent process ID
* Own copy of file descriptors and directory streams.
* process, text, data and other memory locks are NOT inherited.
* process times, in the tms struct
* resource utilizations are set to 0
* pending signals initialized to the empty set
* timers created by timer_create not inherited
* asynchronous input or output operations not inherited
1.1.2 What's the difference between fork() and vfork()?
-------------------------------------------------------
Some systems have a system call `vfork()', which was originally designed as
a lower-overhead version of `fork()'. Since `fork()' involved copying the
entire address space of the process, and was therefore quite expensive, the
`vfork()' function was introduced (in 3.0BSD).
*However*, since `vfork()' was introduced, the implementation of `fork()'
has improved drastically, most notably with the introduction of
`copy-on-write', where the copying of the process address space is
transparently faked by allowing both processes to refer to the same
physical memory until either of them modify it. This largely removes the
justification for `vfork()'; indeed, a large proportion of systems now lack
the original functionality of `vfork()' completely. For compatibility,
though, there may still be a `vfork()' call present, that simply calls
`fork()' without attempting to emulate all of the `vfork()' semantics.
As a result, it is *very* unwise to actually make use of any of the
differences between `fork()' and `vfork()'. Indeed, it is probably unwise
to use `vfork()' at all, unless you know exactly *why* you want to.
The basic difference between the two is that when a new process is created
with `vfork()', the parent process is temporarily suspended, and the child
process might borrow the parent's address space. This strange state of
affairs continues until the child process either exits, or calls
`execve()', at which point the parent process continues.
This means that the child process of a `vfork()' must be careful to avoid
unexpectedly modifying variables of the parent process. In particular, the
child process must *not* return from the function containing the `vfork()'
call, and it must *not* call `exit()' (if it needs to exit, it should use
`_exit()'; actually, this is also true for the child of a normal `fork()').
1.1.3 Why use _exit rather than exit in the child branch of a fork?
-------------------------------------------------------------------
There are a few differences between `exit()' and `_exit()' that become
significant when `fork()', and especially `vfork()', is used.
The basic difference between `exit()' and `_exit()' is that the former
performs clean-up related to user-mode constructs in the library, and calls
user-supplied cleanup functions, whereas the latter performs only the
kernel cleanup for the process.
In the child branch of a `fork()', it is normally incorrect to use
`exit()', because that can lead to stdio buffers being flushed twice, and
temporary files being unexpectedly removed. In C++ code the situation is
worse, because destructors for static objects may be run incorrectly.
(There are some unusual cases, like daemons, where the *parent* should call
`_exit()' rather than the child; the basic rule, applicable in the
overwhelming majority of cases, is that `exit()' should be called only once
for each entry into `main'.)
In the child branch of a `vfork()', the use of `exit()' is even more
dangerous, since it will affect the state of the *parent* process.
1.2 Environment variables
=========================
1.2.1 How can I get/set an environment variable from a program?
---------------------------------------------------------------
Getting the value of an environment variable is done by using `getenv()'.
#include <stdlib.h>
char *getenv(const char *name);
Setting the value of an environment variable is done by using `putenv()'.
#include <stdlib.h>
int putenv(char *string);
The string passed to putenv must *not* be freed or made invalid, since a
pointer to it is kept by `putenv()'. This means that it must either be a
static buffer or allocated off the heap. The string can be freed if the
environment variable is redefined or deleted via another call to `putenv()'.
Remember that environment variables are inherited; each process has a
separate copy of the environment. As a result, you can't change the value
of an environment variable in another process, such as the shell.
Suppose you wanted to get the value for the `TERM' environment variable.
You would use this code:
char *envvar;
envvar=getenv("TERM");
printf("The value for the environment variable TERM is ");
if(envvar)
{
printf("%s\n",envvar);
}
else
{
printf("not set.\n");
}
Now suppose you wanted to create a new environment variable called `MYVAR',
with a value of `MYVAL'. This is how you'd do it.
static char envbuf[256];
sprintf(envbuf,"MYVAR=%s","MYVAL");
if(putenv(envbuf))
{
printf("Sorry, putenv() couldn't find the memory for %s\n",envbuf);
/* Might exit() or something here if you can't live without it */
}
1.2.2 How can I read the whole environment?
-------------------------------------------
If you don't know the names of the environment variables, then the
`getenv()' function isn't much use. In this case, you have to dig deeper
into how the environment is stored.
A global variable, `environ', holds a pointer to an array of pointers to
environment strings, each string in the form `"NAME=value"'. A `NULL'
pointer is used to mark the end of the array. Here's a trivial program to
print the current environment (like `printenv'):
#include <stdio.h>
extern char **environ;
int main()
{
char **ep = environ;
char *p;
while ((p = *ep++))
printf("%s\n", p);
return 0;
}
In general, the `environ' variable is also passed as the third, optional,
parameter to `main()'; that is, the above could have been written:
#include <stdio.h>
int main(int argc, char **argv, char **envp)
{
char *p;
while ((p = *envp++))
printf("%s\n", p);
return 0;
}
However, while pretty universally supported, this method isn't actually
defined by the POSIX standards. (It's also less useful, in general.)
1.3 How can I sleep for less than a second?
===========================================
The `sleep()' function, which is available on all Unixes, only allows for a
duration specified in seconds. If you want finer granularity, then you need
to look for alternatives:
* Many systems have a function `usleep()'
* You can use `select()' or `poll()', specifying no file descriptors to
test; a common technique is to write a `usleep()' function based on
either of these (see the comp.unix.questions FAQ for some examples)
* If your system has itimers (most do), you can roll your own `usleep()'
using them (see the BSD sources for `usleep()' for how to do this)
* If you have POSIX realtime, there is a `nanosleep()' function
Of the above, `select()' is probably the most portable (and strangely, it
is often much more efficient than `usleep()' or an itimer-based method).
However, the behaviour may be different if signals are caught while asleep;
this may or may not be an issue depending on the application.
Whichever route you choose, it is important to realise that you may be
constrained by the timer resolution of the system (some systems allow very
short time intervals to be specified, others have a resolution of, say,
10ms and will round all timings to that). Also, as for `sleep()', the delay
you specify is only a *minimum* value; after the specified period elapses,
there will be an indeterminate delay before your process next gets
scheduled.
1.4 How can I get a finer-grained version of alarm()?
=====================================================
Modern Unixes tend to implement alarms using the `setitimer()' function,
which has a higher resolution and more options than the simple `alarm()'
function. One should generally assume that `alarm()' and
`setitimer(ITIMER_REAL)' may be the same underlying timer, and accessing it
both ways may cause confusion.
Itimers can be used to implement either one-shot or repeating signals;
also, there are generally 3 separate timers available:
`ITIMER_REAL'
counts real (wall clock) time, and sends the `SIGALRM' signal
`ITIMER_VIRTUAL'
counts process virtual (user CPU) time, and sends the `SIGVTALRM'
signal
`ITIMER_PROF'
counts user and system CPU time, and sends the `SIGPROF' signal; it is
intended for interpreters to use for profiling.
Itimers, however, are not part of many of the standards, despite having
been present since 4.2BSD. The POSIX realtime extensions define some
similar, but different, functions.
1.5 How can a parent and child process communicate?
===================================================
A parent and child can communicate through any of the normal inter-process
communication schemes (pipes, sockets, message queues, shared memory), but
also have some special ways to communicate that take advantage of their
relationship as a parent and child.
One of the most obvious is that the parent can get the exit status of the
child.
Since the child inherits file descriptors from its parent, the parent can
open both ends of a pipe, fork, then the parent close one end and the child
close the other end of the pipe. This is what happens when you call the
`popen()' routine to run another program from within yours, i.e. you can
write to the file descriptor returned from `popen()' and the child process
sees it as its stdin, or you can read from the file descriptor and see what
the program wrote to its stdout. (The mode parameter to `popen()' defines
which; if you want to do both, then you can do the plumbing yourself
without too much difficulty.)
Also, the child process inherits memory segments mmapped anonymously (or by
mmapping the special file `/dev/zero') by the parent; these shared memory
segments are not accessible from unrelated processes.
1.6 How do I get rid of zombie processes?
=========================================
1.6.1 What is a zombie?
-----------------------
When a program forks and the child finishes before the parent, the kernel
still keeps some of its information about the child in case the parent
might need it - for example, the parent may need to check the child's exit
status. To be able to get this information, the parent calls `wait()';
when this happens, the kernel can discard the information.
In the interval between the child terminating and the parent calling
`wait()', the child is said to be a `zombie'. (If you do `ps', the child
will have a `Z' in its status field to indicate this.) Even though it's
not running, it's still taking up an entry in the process table. (It
consumes no other resources, but some utilities may show bogus figures for
e.g. CPU usage; this is because some parts of the process table entry have
been overlaid by accounting info to save space.)
This is not good, as the process table has a fixed number of entries and it
is possible for the system to run out of them. Even if the system doesn't
run out, there is a limit on the number of processes each user can run,
which is usually smaller than the system's limit. This is one of the
reasons why you should always check if `fork()' failed, by the way!
If the parent terminates without calling wait(), the child is `adopted' by
`init', which handles the work necessary to cleanup after the child. (This
is a special system program with process ID 1 - it's actually the first
program to run after the system boots up).
1.6.2 How do I prevent them from occuring?
------------------------------------------
You need to ensure that your parent process calls `wait()' (or `waitpid()',
`wait3()', etc.) for every child process that terminates; or, on some
systems, you can instruct the system that you are uninterested in child
exit states.
Another approach is to `fork()' *twice*, and have the immediate child
process exit straight away. This causes the grandchild process to be
orphaned, so the init process is responsible for cleaning it up. For code
to do this, see the function `fork2()' in the examples section.
To ignore child exit states, you need to do the following (check your
system's manpages to see if this works):
struct sigaction sa;
sa.sa_handler = SIG_IGN;
#ifdef SA_NOCLDWAIT
sa.sa_flags = SA_NOCLDWAIT;
#else
sa.sa_flags = 0;
Wednesday, April 21, 2010
interview questions on algorithms
http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm
Algorithms
- What's the difference between a linked list and an array?
- Implement a linked list. Why did you pick the method you did?
- Implement an algorithm to sort a linked list. Why did you pick the method you did? Now do it in O(n) time.
- Describe advantages and disadvantages of the various stock sorting algorithms.
- Implement an algorithm to reverse a linked list. Now do it without recursion.
- Implement an algorithm to insert a node into a circular linked list without traversing it.
- Implement an algorithm to sort an array. Why did you pick the method you did?
- Implement an algorithm to do wild card string matching.
- Implement strstr() (or some other string library function).
- Reverse a string. Optimize for speed. Optimize for space.
- Reverse the words in a sentence, i.e. "My name is Chris" becomes "Chris is name My." Optimize for speed. Optimize for space.
- Find a substring. Optimize for speed. Optimize for space.
- Compare two strings using O(n) time with constant space.
- Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?
- Count the number of set bits in a number. Now optimize for speed. Now optimize for size.
- Multiple by 8 without using multiplication or addition. Now do the same with 7.
- Add numbers in base n (not any of the popular ones like 10, 16, 8 or 2 -- I hear that Charles Simonyi, the inventor of Hungarian Notation, favors -2 when asking this question).
- Write routines to read and write a bounded buffer.
- Write routines to manage a heap using an existing array.
- Implement an algorithm to take an array and return one with only unique elements in it.
- Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Now speed it up. Now test it.
- Implement an algorithm to print out all files below a given root node.
- Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.
- How would you find a cycle in a linked list?
- Give me an algorithm to shuffle a deck of cards, given that the cards are stored in an array of ints.
- The following asm block performs a common math function, what is it?
cwd xor ax, dx
sub ax, dx - Imagine this scenario:
I/O completion ports are communictaions ports which take handles to files, sockets, or any other I/O. When a Read or Write is submitted to them, they cache the data (if necessary), and attempt to take the request to completion. Upon error or completion, they call a user-supplied function to let the users application know that that particular request has completed. They work asynchronously, and can process an unlimited number of simultaneous requests.
Design the implementation and thread models for I/O completion ports. Remember to take into account multi-processor machines. - Write a function that takes in a string parameter and checks to see whether or not it is an integer, and if it is then return the integer value.
- Write a function to print all of the permutations of a string.
- Implement malloc.
- Write a function to print the Fibonacci numbers.
- Write a function to copy two strings, A and B. The last few bytes of string A overlap the first few bytes of string B.
- How would you write qsort?
- How would you print out the data in a binary tree, level by level, starting at the top?
--
an alternate us % modulus
Ah, the joys of bitwise arithmetic. A side effect of many division routines is the modulus - so in few cases should division actually be faster than modulus. I'm interested to see the source you got this information from. Processors with multipliers have interesting division routines using the multiplier, but you can get from division result to modulus with just another two steps (multiply and subtract) so it's still comparable. If the processor has a built in division routine you'll likely see it also provides the remainder.
Still, there is a small branch of number theory devoted to Modular Arithmetic which requires study if you really want to understand how to optimize a modulus operation. Modular arithmatic, for instance, is very handy for generating magic squares.
So, in that vein, here's a very low level look at the math of modulus for an example of x, which should show you how simple it can be compared to division.
Maybe a better way to think about the problem is in terms of number
bases and modulo arithmetic. For example, your goal is to compute DOW
mod 7 where DOW is the 16-bit representation of the day of the
week. You can write this as:
DOW = DOW_HI*256 + DOW_LO
DOW%7 = (DOW_HI*256 + DOW_LO) % 7
= ((DOW_HI*256)%7 + (DOW_LO % 7)) %7
= ((DOW_HI%7 * 256%7) + (DOW_LO%7)) %7
= ((DOW_HI%7 * 4) + (DOW_LO%7)) %7
Expressed in this manner, you can separately compute the modulo 7
result for the high and low bytes. Multiply the result for the high by
4 and add it to the low and then finally compute result modulo 7.
Computing the mod 7 result of an 8-bit number can be performed in a
similar fashion. You can write an 8-bit number in octal like so:
X = a*64 + b*8 + c
Where a, b, and c are 3-bit numbers.
X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7
= (a%7 + b%7 + c%7) % 7
= (a + b + c) % 7
since 64%7 = 8%7 = 1
Of course, a, b, and c are
c = X & 7
b = (X>>3) & 7
a = (X>>6) & 7 (actually, a is only 2-bits).
The largest possible value for a+b+c is 7+7+3 = 17. So, you'll need
one more octal step. The complete (untested) C version could be
written like:
unsigned char Mod7Byte(unsigned char X)
{
X = (X&7) + ((X>>3)&7) + (X>>6);
X = (X&7) + (X>>3);
return X==7 ? 0 : X;
}
I spent a few moments writing a PIC version. The actual implementation
is slightly different than described above
Mod7Byte:
movwf temp1 ;
andlw 7 ;W=c
movwf temp2 ;temp2=c
rlncf temp1,F ;
swapf temp1,W ;W= a*8+b
andlw 0x1F
addwf temp2,W ;W= a*8+b+c
movwf temp2 ;temp2 is now a 6-bit number
andlw 0x38 ;get the high 3 bits == a'
xorwf temp2,F ;temp2 now has the 3 low bits == b'
rlncf WREG,F ;shift the high bits right 4
swapf WREG,F ;
addwf temp2,W ;W = a' + b'
; at this point, W is between 0 and 10
addlw -7
bc Mod7Byte_L2
Mod7Byte_L1:
addlw 7
Mod7Byte_L2:
return
Here's a liitle routine to test the algorithm
clrf x
clrf count
TestLoop:
movf x,W
RCALL Mod7Byte
cpfseq count
bra fail
incf count,W
xorlw 7
skpz
xorlw 7
movwf count
incfsz x,F
bra TestLoop
passed:
Finally, for the 16-bit result (which I have not tested), you could
write:
uint16 Mod7Word(uint16 X)
{
return Mod7Byte(Mod7Byte(X & 0xff) + Mod7Byte(X>>8)*4);
}
Scott
--
Siva
9886179349
Monday, April 19, 2010
SCTP -stream control transmission protocol
http://www.javvin.com/protocolSCTP.html
SCTP: Stream Control Transmission Protocol
Stream Control Transmission Protocol (SCTP), a part of the Signalling Transport (SIGTRAN) protocol family, was designed to transport PSTN signalling messages over IP networks, but is capable of broader applications. SCTP is a reliable transport protocol operating on top of a connectionless packet network such as IP. SCTP is designed to address the limitations and complexity of TCP while transporting real time signaling and data such as PSTN SS7/C7 signaling over IP network. SCTP can also run on top of the UDP layer.
SCTP offers the following services:
- acknowledged error-free non-duplicated transfer of user data,
- data fragmentation to conform to discovered path MTU size,
- sequenced delivery of user messages within multiple streams, with an option for order-of-arrival delivery of individual user messages,
- optional bundling of multiple user messages into a single SCTP packet, and
- network-level fault tolerance through supporting of multi homing at either or both ends of an association.
The design of SCTP includes appropriate congestion avoidance behavior and resistance to flooding and masquerade attacks. The SCTP datagram is comprised of a common header and chunks. The chunks contain either control information or user data.
Stream Control Transmission Protocol (SCTP), a core protocol in the SIGTRAN protocol stack, provides transport layer services over IP for SS7/C7. Examples of such transport include: transport of signaling between a Signaling Gateway and Media Gateway or Media Gateway Controller; transport of signaling ("backhaul") from a Media Gateway to a Media Gateway Controller; transport of TCAP between a Signaling Gateway and other IP nodes.
SCTP has also other non-signalling applications such as:
o Transport of Authentication, Authorization and Accounting (AAA) information.
o Transport of Block Storage traffic (examples SCSI, Fibre Channel...)
o Transport of Remote Direct Data Placement traffic.
o Transport of Reliable Server poolling traffic.
o Transport of IP Flow information export traffic.
|
Protocol Structure - SCTP: Stream Control Transmission Protocol
| 16 | 32bit |
| Source Port Number | Destination Port Number |
| Verification Tag | |
| Checksum | |
- Source Port Number - SCTP sender's port number. It can be used by the receiver, in combination with the source IP Address, to identify the association to which this datagram belongs.
- Destination Port Number - Destination port number where SCTP datagram intended to go. The receiving host will use this port number to de-multiplex the SCTP datagram to the correct receiving endpoint/application.
- Verification Tag - The receiver uses the Verification tag to identify the association. On transmit, the value of this Verification tag must be set to the value of the Initiate tag received from the peer endpoint during the association initialization.
- Checksum - This field contains an Adler-32 checksum on this SCTP datagram.
Related Protocols
UDP , TCP , IP , SS7/C7, SIGTRAN
Sponsor Source
SCTP is defined by IETF (http://www.ietf.org ) in RFC 2690.
Thursday, April 15, 2010
Hard Link vs Soft link
http://linuxgazette.net/105/pitcher.html
Q: Can someone give me a simple explanation of the difference between a soft link and a hard link? The documentation I've read mention these links but make no strong explanations of their meaning and how/when to use them. Thanks!
A: OK, I'll give it a try...
Unix files consist of two parts: the data part and the filename part.
The data part is associated with something called an 'inode'. The inode carries the map of where the data is, the file permissions, etc. for the data.
.---------------> ! data ! ! data ! etc
/ +------+ !------+
! permbits, etc ! data addresses !
+------------inode---------------+
The filename part carries a name and an associated inode number.
.--------------> ! permbits, etc ! addresses !
/ +---------inode-------------+
! filename ! inode # !
+--------------------+
More than one filename can reference the same inode number; these files are said to be 'hard linked' together.
! filename ! inode # !
+--------------------+
\
>--------------> ! permbits, etc ! addresses !
/ +---------inode-------------+
! othername ! inode # !
+---------------------+
On the other hand, there's a special file type whose data part carries a path to another file. Since it is a special file, the OS recognizes the data as a path, and redirects opens, reads, and writes so that, instead of accessing the data within the special file, they access the data in the file named by the data in the special file. This special file is called a 'soft link' or a 'symbolic link' (aka a 'symlink').
! filename ! inode # !
+--------------------+
\
.-------> ! permbits, etc ! addresses !
+---------inode-------------+
/
/
/
.----------------------------------------------'
(
'--> !"/path/to/some/other/file"!
+---------data-------------+
/ }
.~ ~ ~ ~ ~ ~ ~ }-- (redirected at open() time)
( }
'~~> ! filename ! inode # !
+--------------------+
\
'------------> ! permbits, etc ! addresses !
+---------inode-------------+
/
/
.----------------------------------------------------'
(
'-> ! data ! ! data ! etc.
+------+ +------+
Now, the filename part of the file is stored in a special file of its own along with the filename parts of other files; this special file is called a directory. The directory, as a file, is just an array of filename parts of other files.
When a directory is built, it is initially populated with the filename parts of two special files: the '.' and '..' files. The filename part for the '.' file is populated with the inode# of the directory file in which the entry has been made; '.' is a hardlink to the file that implements the current directory.
The filename part for the '..' file is populated with the inode# of the directory file that contains the filename part of the current directory file. '..' is a hardlink to the file that implements the immediate parent of the current directory.
The 'ln' command knows how to build hardlinks and softlinks; the 'mkdir' command knows how to build directories (the OS takes care of the above hardlinks).
There are restrictions on what can be hardlinked (both links must reside on the same filesystem, the source file must exist, etc.) that are not applicable to softlinks (source and target can be on seperate file systems, source does not have to exist, etc.). OTOH, softlinks have other restrictions not shared by hardlinks (additional I/O necessary to complete file access, additional storage taken up by softlink file's data, etc.)
In other words, there's tradeoffs with each.
Now, let's demonstrate some of this...
Tuesday, April 13, 2010
2010 CWE/SANS Top 25 Most Dangerous Programming Errors
http://cwe.mitre.org/top25/#CWE-120
| [1] | 346 | Failure to Preserve Web Page Structure ('Cross-site Scripting') | |
| [2] | 330 | Improper Sanitization of Special Elements used in an SQL Command ('SQL Injection') | |
| [3] | 273 | Buffer Copy without Checking Size of Input ('Classic Buffer Overflow') | |
| [4] | 261 | Cross-Site Request Forgery (CSRF) | |
| [5] | 219 | Improper Access Control (Authorization) | |
| [6] | 202 | Reliance on Untrusted Inputs in a Security Decision | |
| [7] | 197 | Improper Limitation of a Pathname to a Restricted Directory ('Path Traversal') | |
| [8] | 194 | Unrestricted Upload of File with Dangerous Type | |
| [9] | 188 | Improper Sanitization of Special Elements used in an OS Command ('OS Command Injection') | |
| [10] | 188 | Missing Encryption of Sensitive Data | |
| [11] | 176 | Use of Hard-coded Credentials | |
| [12] | 158 | Buffer Access with Incorrect Length Value | |
| [13] | 157 | Improper Control of Filename for Include/Require Statement in PHP Program ('PHP File Inclusion') | |
| [14] | 156 | Improper Validation of Array Index | |
| [15] | 155 | Improper Check for Unusual or Exceptional Conditions | |
| [16] | 154 | Information Exposure Through an Error Message | |
| [17] | 154 | Integer Overflow or Wraparound | |
| [18] | 153 | Incorrect Calculation of Buffer Size | |
| [19] | 147 | Missing Authentication for Critical Function | |
| [20] | 146 | Download of Code Without Integrity Check | |
| [21] | 145 | Incorrect Permission Assignment for Critical Resource | |
| [22] | 145 | Allocation of Resources Without Limits or Throttling | |
| [23] | 142 | URL Redirection to Untrusted Site ('Open Redirect') | |
| [24] | 141 | Use of a Broken or Risky Cryptographic Algorithm | |
| [25] | 138 | Race Condition |
Cross-site scripting and SQL injection are the 1-2 punch of security weaknesses in 2010. Even when a software package doesn't primarily run on the web, there's a good chance that it has a web-based management interface or HTML-based output formats that allow cross-site scripting. For data-rich software applications, SQL injection is the means to steal the keys to the kingdom. The classic buffer overflow comes in third, while more complex buffer overflow variants are sprinkled in the rest of the Top 25.
Category-Based View of the Top 25
This section sorts the entries into the three high-level categories that were used in the 2009 Top 25:
· Insecure Interaction Between Components
· Risky Resource Management
· Porous Defenses
Insecure Interaction Between Components
These weaknesses are related to insecure ways in which data is sent and received between separate components, modules, programs, processes, threads, or systems.
For each weakness, its ranking in the general list is provided in square brackets.
| Rank | CWE ID | Name |
| [1] | Failure to Preserve Web Page Structure ('Cross-site Scripting') | |
| [2] | Improper Sanitization of Special Elements used in an SQL Command ('SQL Injection') | |
| [4] | Cross-Site Request Forgery (CSRF) | |
| [8] | Unrestricted Upload of File with Dangerous Type | |
| [9] | Improper Sanitization of Special Elements used in an OS Command ('OS Command Injection') | |
| [17] | Information Exposure Through an Error Message | |
| [23] | URL Redirection to Untrusted Site ('Open Redirect') | |
| [25] | Race Condition |
Risky Resource Management
The weaknesses in this category are related to ways in which software does not properly manage the creation, usage, transfer, or destruction of important system resources.
| Rank | CWE ID | Name |
| [3] | Buffer Copy without Checking Size of Input ('Classic Buffer Overflow') | |
| [7] | Improper Limitation of a Pathname to a Restricted Directory ('Path Traversal') | |
| [12] | Buffer Access with Incorrect Length Value | |
| [13] | Improper Check for Unusual or Exceptional Conditions | |
| [14] | Improper Control of Filename for Include/Require Statement in PHP Program ('PHP File Inclusion') | |
| [15] | Improper Validation of Array Index | |
| [16] | Integer Overflow or Wraparound | |
| [18] | Incorrect Calculation of Buffer Size | |
| [20] | Download of Code Without Integrity Check | |
| [22] | Allocation of Resources Without Limits or Throttling |
Porous Defenses
The weaknesses in this category are related to defensive techniques that are often misused, abused, or just plain ignored.
| Rank | CWE ID | Name |
| [5] | Improper Access Control (Authorization) | |
| [6] | Reliance on Untrusted Inputs in a Security Decision | |
| [10] | Missing Encryption of Sensitive Data | |
| [11] | Use of Hard-coded Credentials | |
| [19] | Missing Authentication for Critical Function | |
| [21] | Incorrect Permission Assignment for Critical Resource | |
| [24] | Use of a Broken or Risky Cryptographic Algorithm |
The prioritization of items in the general Top 25 list is just that - general. The rankings, and even the selection of which items should be included, can vary widely depending on context. Ideally, each organization can decide how to rank weaknesses based on its own criteria, instead of relying on a single general-purpose list.
A separate document provides several "focus profiles" with their own criteria for selection and ranking, which may be more useful than the general list.
| Name | Description |
| From the original nominee list of 41 submitted CWE entries, the Top 25 was selected. This "On the Cusp" profile includes the remaining 16 weaknesses that did not make it into the final Top 25. | |
| This profile ranks weaknesses that are important from an educational perspective within a school or university context. It focuses on the CWE entries that graduating students should know, including historically important weaknesses. | |
| This profile specifies which weaknesses appear in which programming languages. Notice that most weaknesses are actually language-independent, although they may be more prevalent in one language or another. | |
| This profile lists weaknesses that are typically fixed in design or implementation. | |
| This profile highlights which weaknesses can be detected using automated versus manual analysis. Currently, there is very little public, authoritative information about the efficacy of these methods and their utility. There are many competing opinions, even among experts. As a result, these ratings should only be treated as guidelines, not rules. | |
| This profile is for developers who have already established security in their practice. It uses votes from the major developers who contributed to the Top 25. | |
| This profile ranks weaknesses based primarily on their importance, as determined from the base voting data that was used to create the general list. Prevalence is included in the scores, but it has much less weighting than importance. | |
| This profile lists weaknesses based on their technical impact, i.e., what an attacker can accomplish by exploiting each weakness. |
For each individual weakness entry, additional information is provided. The primary audience is intended to be software programmers and designers.
| Ranking | The ranking of the weakness in the general list. |
| Score Summary | A summary of the individual ratings and scores that were given to this weakness, including Prevalence, Importance, and Adjusted Score. |
| CWE ID and name | CWE identifier and short name of the weakness |
| Supporting Information | Supplementary information about the weakness that may be useful for decision-makers to further prioritize the entries. |
| Discussion | Short, informal discussion of the nature of the weakness and its consequences. The discussion avoids digging too deeply into technical detail. |
| Prevention and Mitigations | Steps that developers can take to mitigate or eliminate the weakness. Developers may choose one or more of these mitigations to fit their own needs. Note that the effectiveness of these techniques vary, and multiple techniques may be combined for greater defense-in-depth. |
| Related CWEs | Other CWE entries that are related to the Top 25 weakness. Note: This list is illustrative, not comprehensive. |
| General Parent | One or more pointers to more general CWE entries, so you can see the breadth and depth of the problem. |
| Related Attack Patterns | CAPEC entries for attacks that may be successfully conducted against the weakness. Note: the list is not necessarily complete. |
| Other pointers | Links to more details including source code examples that demonstrate the weakness, methods for detection, etc. |
Supporting Information
Each Top 25 entry includes supporting data fields for weakness prevalence, technical impact, and other information. Each entry also includes the following data fields.
| Field | Description |
| Attack Frequency | How often the weakness occurs in vulnerabilities that are exploited by an attacker. |
| Ease of Detection | How easy it is for an attacker to find this weakness. |
| Remediation Cost | The amount of effort required to fix the weakness. |
| Attacker Awareness | The likelihood that an attacker is going to be aware of this particular weakness, methods for detection, and methods for exploitation. |
See Appendix A for more details.
This section provides details for each individual CWE entry, along with links to additional information. See the Organization of the Top 25 section for an explanation of the various fields.
| CWE-79: Failure to Preserve Web Page Structure ('Cross-site Scripting') |
Summary
| Weakness Prevalence | High | | Consequences | Code execution, Security bypass |
| Remediation Cost | Low | | Ease of Detection | Easy |
| Attack Frequency | Often | | Attacker Awareness | High |
Subscribe to:
Posts (Atom)