import random
def binarySearch(alist, searchelement):
'''
binartsearch using divide and conqure(non-recursive).
@param: alist, unsorted list
@param: item, an element to be searched in alist
returns: bool, position, the presence of item in alist and position.
'''
first = 0
found = False
adict={}
pos=0
for i in range(len(alist)):
adict[alist[i]]=alist.index(alist[i])+1
alist.sort()
last = len(alist)-1
while first<=last and not found:
midpoint = (first+last)//2
if alist[midpoint]==searchelement:
found = True
pos=adict[searchelement]
else:
if searchelement<alist[midpoint]:
last=midpoint-1
else:
first=midpoint+1
return found,pos
alist = [random.randint(0,99) for i in range(100)]
print alist
searchelement = raw_input("Enter element to be Searched: ")
print(binarySearch(alist,int(searchelement)))
s = raw_input("enter few elements ")
alist = s.split(",")
findEle = raw_input("enter element to be searched ")
print(binarySearch(alist,findEle))
binary search runs in at worst logarithmic time, making O(log n) comparisons, where n is the number of elements in the array
Algorithm
Binary search only works on sorted arrays. A binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less or more than the middle element, the search continues the lower or upper half of the array respectively with a new middle element, eliminating the other half from consideration. This method can be described recursively or iteratively.
Procedure[edit]
Given an array A of n elements with values or records A0 ... An−1 and target value T, the following subroutine uses binary search to find the index of T in A.[6]
1. Set L to 0 and R to n−1.
2. If L > R, the search terminates as unsuccessful. Set m (the position of the middle element) to the floor of (L + R) / 2.
3. If Am = T, the search is done; return m.
4. If Am < T, set L to m + 1 and go to step 2.
5. If Am > T, set R to m – 1 and go to step 2.
6. This iterative procedure keeps track of the search boundaries via two variables; a recursive version would keep its boundaries in its recursive calls. Some implementations may place the comparison for equality at the end, resulting in a faster comparison loop but costing one more iteration on average.[7]
from xml.dom.minidom import parse
import xml.dom.minidom
import random
import sys
from threading import Thread, current_thread
def quickSort(alist):
quickSortHelper(alist,0,len(alist)-1)
def quickSortHelper(alist,first,last):
if first<last:
splitpoint = partition(alist,first,last)
t =Thread(target = quickSortHelper, args = (alist,first,splitpoint-1))
t.start()
t.join()
t1=Thread(target = quickSortHelper, args = (alist,splitpoint+1,last))
t1.start()
t1.join()
return alist
def partition(alist,first,last):
pivotvalue = alist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
leftmark = leftmark + 1
while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark = rightmark -1
if rightmark < leftmark:
done = True
else:
swap(alist,leftmark,rightmark)
swap(alist,first,rightmark)
return rightmark
def swap(alist,left,right):
temp = alist[left]
alist[left] = alist[right]
alist[right] = temp
def genXML(filename):
alist = [random.randint(1,100) for i in range(50)]
f = open(filename,"w")
f.write("<Number>")
for i in range(len(alist)):
f.write("\n\t<integer>"+str(alist[i])+"</integer>")
f.write("\n</Number>")
f.close()
if __name__ == '__main__':
filename = raw_input("Enter filename: ")
filename = filename if filename.find("xml")!=-1 else filename+".xml"
genXML(filename)
DOMTree = xml.dom.minidom.parse(filename)
collection = DOMTree.documentElement
integers = collection.getElementsByTagName("integer")
alist=[]
for i in range(len(integers)):
val = collection.getElementsByTagName("integer")[i]
alist.append(int(val.childNodes[0].data))
quickSort(alist)
print(alist)
Mathematical analysis of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.
Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
The steps are:
1. Pick an element, called a pivot, from the array.
2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
The base case of the recursion is arrays of size zero or one, which never need to be sorted.
The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance.
import bitstring
from bitstring import BitArray
from flask import Flask, request, render_template
def booths(m,r):
x=len(bin(m))
y=len(bin(r))
totallength = x+y+1
if m<0 and r<0 or r<0:
bugbit = 1
else:
bugbit = 0
A = BitArray(int = m,length = totallength) << (y+1)
compliment = BitArray(int = -m,length = totallength) << (y+1)
P = BitArray(int = r, length = totallength)
P = P<<1
for i in range(1,y+1):
if P[-2:]=='0b01':
P = BitArray(int = P.int + A.int, length = totallength)
elif P[-2:]=='0b10':
P = BitArray(int = P.int + compliment.int, length = totallength)
P = BitArray(int = P.int>>1, length = totallength)
P = P[:-1]
P.int = P.int + bugbit
steps =""
return '<h1>RESULT</h1><br>'+steps+'<br><h3>decimal value: '+str(P.int)+'</br><br> binary value: '+str(P.bin)+"</h3>"
#print(booths(12,13))
app = Flask(__name__)
@app.route('/')
def rend():
return render_template("booths.html")
@app.route('/',methods=['POST'])
def post_method():
m = request.form['multiplier']
r = request.form['multiplicand']
try:
multiplier = int(m)
multiplicand = int(r)
except:
return "<br><h1>Error</h1><br> One of the item found"
print multiplier, multiplicand
return booths(multiplier,multiplicand)
if __name__ == '__main__':
app.run(debug=True)
#html file: templates/booths.html
<!DOCTYPE html>
<html>
<body>
<h1>Booth's Multiplier</h1>
<h2>Enter two numbers </h2>
<form action="." method = "POST">
<input type="number" name="multiplier">*
<input type="number" name="multiplicand">
<input type="submit" name="myform" value="=">
</form>
<body>
<html>
Booth's algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in m and r.
1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
1.1 A: Fill the most significant (leftmost) bits with the value of m. Fill the remaining (y + 1) bits with zeros.
1.2 S: Fill the most significant bits with the value of (−m) in two's complement notation. Fill the remaining (y + 1) bits with zeros.
1.3. P: Fill the most significant x bits with zeros. To the right of this, append the value of r. Fill the least significant (rightmost) bit with a zero.
2. Determine the two least significant (rightmost) bits of P.
2.1 If they are 01, find the value of P + A. Ignore any overflow.
2.2 If they are 10, find the value of P + S. Ignore any overflow.
2.3 If they are 00, do nothing. Use P directly in the next step.
2.4 If they are 11, do nothing. Use P directly in the next step.
3. Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let P now equal this new value.
4. Repeat steps 2 and 3 until they have been done y times.
5. Drop the least significant (rightmost) bit from P. This is the product of m and r.
multiplying −8 by 2 using 4 bits for the multiplicand and the multiplier:
A = 1 1000 0000 0
S = 0 1000 0000 0
P = 0 0000 0010 0
Perform the loop four times:
P = 0 0000 0010 0. The last two bits are 00.
P = 0 0000 0001 0. Right shift.
P = 0 0000 0001 0. The last two bits are 10.
P = 0 1000 0001 0. P = P + S.
P = 0 0100 0000 1. Right shift.
P = 0 0100 0000 1. The last two bits are 01.
P = 1 1100 0000 1. P = P + A.
P = 1 1110 0000 0. Right shift.
P = 1 1110 0000 0. The last two bits are 00.
P = 1 1111 0000 0. Right shift.
The product is 11110000 (after discarding the first and the last bit) which is −16.
from pymongo import MongoClient
import threading
import random
import time
class Philosopher(threading.Thread):
running = True
def __init__(self, xname, forkOnLeft, forkOnRight):
threading.Thread.__init__(self)
self.name = xname
self.forkOnLeft = forkOnLeft
self.forkOnRight = forkOnRight
def run(self):
while(self.running):
# Philosopher is thinking (but really is sleeping).
time.sleep( random.uniform(3,13))
insertIntoMongo( self.name, 'is hungry')
self.dine()
def dine(self):
fork1, fork2 = self.forkOnLeft, self.forkOnRight
while self.running:
fork1.acquire(True)
locked = fork2.acquire(False)
if locked: break
fork1.release()
insertIntoMongo( self.name, 'swaps forks')
fork1, fork2 = fork2, fork1
else:
return
self.dining()
fork2.release()
fork1.release()
def dining(self):
insertIntoMongo( self.name, 'starts eating' )
time.sleep(random.uniform(1,10))
insertIntoMongo( self.name, 'finishes eating and leaves to think.')
def DiningPhilosophers():
forks = [threading.Lock() for n in range(5)]
philosopherNames = ('Aristotle','Kant','Buddha','Marx', 'Russel')
philosophers= [Philosopher(philosopherNames[i], forks[i%5], forks[(i+1)%5]) \
for i in range(5)]
random.seed(507129)
Philosopher.running = True
for p in philosophers: p.start()
time.sleep(100)
Philosopher.running = False
insertIntoMongo( 'Exit', 'Now we are finishing.')
def insertIntoMongo(key,value):
result = db.diningCol.insert_one(
{
key: value
} )
client = MongoClient("mongodb://127.0.0.1:27027")
db = client.test
db.drop_collection("diningCol")
DiningPhilosophers()
cursor = db.diningCol.find()
for document in cursor:
document.pop(u'_id')
for key,value in document.items():
print key + " " +value
start the server
mongod --dbpath /home/cipher/mongodb --port 27027 --bind_ip 127.0.0.1 --noprealloc
#Dining philosophers
The dining philosophers problem illustrates non-composability of low-level synchronization primitives like semaphores. It is a modification of a problem posed by Edsger Dijkstra.
Five philosophers, Aristotle, Kant, Spinoza, Marx, and Russell (the tasks) spend their time thinking and eating spaghetti. They eat at a round table with five individual seats. For eating each philosopher needs two forks (the resources). There are five forks on the table, one left and one right of each seat. When a philosopher cannot grab both forks it sits and waits. Eating takes random time, then the philosopher puts the forks down and leaves the dining room. After spending some random time thinking about the nature of the universe, he again becomes hungry, and the circle repeats itself.
It can be observed that a straightforward solution, when forks are implemented by semaphores, is exposed to deadlock. There exist two deadlock states when all five philosophers are sitting at the table holding one fork each. One deadlock state is when each philosopher has grabbed the fork left of him, and another is when each has the fork on his right.
# This solution avoids deadlock by never waiting for a fork while having one in hand.
# If a philosopher acquires one fork but can't acquire the second,
# he releases the first fork before waiting to acquire the other (which then becomes the first fork acquired).
# Dining philosophers, 5 Phillies with 5 forks. Must have two forks to eat.
#
# Deadlock is avoided by never waiting for a fork while holding a fork (locked)
# Procedure is to do block while waiting to get first fork, and a nonblocking
# acquire of second fork. If failed to get second fork, release first fork,
# swap which fork is first and which is second and retry until getting both.
#
Create a new Android Application Project. Let's say your Application Name is "Calculator", your Project Name is "Calculator", and your Package Name is "com.example.calculator". Setup the project with the default settings. Now replace MainActivity.java, activity_main.xml (in res/layout), & strings.xml (in res/values) with the code below. Next, create a new class "CalculatorBrain" and replace CalculatorBrain.java with the code below.
compileSdkVersion 23 buildToolsVersion "21.1.2"
The calculator should run without errors! MainActivity.java
package example.com.calculator;
import java.io.IOException;
import java.text.DecimalFormat;
import android.annotation.SuppressLint;
import android.app.Activity;
import android.os.Bundle;
import android.view.View;
import android.view.View.OnClickListener;
import android.view.Window;
import android.view.WindowManager;
import android.widget.Button;
import android.widget.TextView;
/**
* Created by neeraj on 19-03-2016.
*/
public class MainActivity extends Activity implements OnClickListener {
private TextView mCalculatorDisplay;
private Boolean userIsInTheMiddleOfTypingANumber = false;
private CalculatorBrain mCalculatorBrain;
private static final String DIGITS = "0123456789.";
DecimalFormat df = new DecimalFormat("@###########");
@SuppressLint("NewApi")
@Override
protected void onCreate(Bundle savedInstanceState) {
// hide the window title.
requestWindowFeature(Window.FEATURE_NO_TITLE);
// hide the status bar and other OS-level chrome
getWindow().addFlags(WindowManager.LayoutParams.FLAG_FULLSCREEN);
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
mCalculatorBrain = new CalculatorBrain();
mCalculatorDisplay = (TextView) findViewById(R.id.textView1);
df.setMinimumFractionDigits(0);
df.setMinimumIntegerDigits(1);
df.setMaximumIntegerDigits(8);
findViewById(R.id.button0).setOnClickListener(this);
findViewById(R.id.button1).setOnClickListener(this);
findViewById(R.id.button2).setOnClickListener(this);
findViewById(R.id.button3).setOnClickListener(this);
findViewById(R.id.button4).setOnClickListener(this);
findViewById(R.id.button5).setOnClickListener(this);
findViewById(R.id.button6).setOnClickListener(this);
findViewById(R.id.button7).setOnClickListener(this);
findViewById(R.id.button8).setOnClickListener(this);
findViewById(R.id.button9).setOnClickListener(this);
findViewById(R.id.buttonAdd).setOnClickListener(this);
findViewById(R.id.buttonSubtract).setOnClickListener(this);
findViewById(R.id.buttonMultiply).setOnClickListener(this);
findViewById(R.id.buttonDivide).setOnClickListener(this);
findViewById(R.id.buttonToggleSign).setOnClickListener(this);
findViewById(R.id.buttonDecimalPoint).setOnClickListener(this);
findViewById(R.id.buttonEquals).setOnClickListener(this);
findViewById(R.id.buttonClear).setOnClickListener(this);
findViewById(R.id.buttonClearMemory).setOnClickListener(this);
findViewById(R.id.buttonAddToMemory).setOnClickListener(this);
findViewById(R.id.buttonSubtractFromMemory).setOnClickListener(this);
findViewById(R.id.buttonRecallMemory).setOnClickListener(this);
// The following buttons only exist in layout-land (Landscape mode) and require extra attention.
// The messier option is to place the buttons in the regular layout too and set android:visibility="invisible".
if (findViewById(R.id.buttonSquareRoot) != null) {
findViewById(R.id.buttonSquareRoot).setOnClickListener(this);
}
if (findViewById(R.id.buttonSquared) != null) {
findViewById(R.id.buttonSquared).setOnClickListener(this);
}
if (findViewById(R.id.buttonInvert) != null) {
findViewById(R.id.buttonInvert).setOnClickListener(this);
}
if (findViewById(R.id.buttonSine) != null) {
findViewById(R.id.buttonSine).setOnClickListener(this);
}
if (findViewById(R.id.buttonCosine) != null) {
findViewById(R.id.buttonCosine).setOnClickListener(this);
}
if (findViewById(R.id.buttonTangent) != null) {
findViewById(R.id.buttonTangent).setOnClickListener(this);
}
}
@Override
public void onClick(View v) {
String buttonPressed = ((Button) v).getText().toString();
if (DIGITS.contains(buttonPressed)) {
// digit was pressed
if (userIsInTheMiddleOfTypingANumber) {
if (buttonPressed.equals(".") && mCalculatorDisplay.getText().toString().contains(".")) {
// ERROR PREVENTION
// Eliminate entering multiple decimals
} else {
mCalculatorDisplay.append(buttonPressed);
}
} else {
if (buttonPressed.equals(".")) {
// ERROR PREVENTION
// This will avoid error if only the decimal is hit before an operator, by placing a leading zero
// before the decimal
mCalculatorDisplay.setText(0 + buttonPressed);
} else {
mCalculatorDisplay.setText(buttonPressed);
}
userIsInTheMiddleOfTypingANumber = true;
}
} else {
// operation was pressed
if (userIsInTheMiddleOfTypingANumber) {
mCalculatorBrain.setOperand(Double.parseDouble(mCalculatorDisplay.getText().toString()));
userIsInTheMiddleOfTypingANumber = false;
}
try {
mCalculatorBrain.performOperation(buttonPressed);
} catch (IOException e) {
e.printStackTrace();
}
mCalculatorDisplay.setText(df.format(mCalculatorBrain.getResult()));
}
}
@Override
protected void onSaveInstanceState(Bundle outState) {
super.onSaveInstanceState(outState);
// Save variables on screen orientation change
outState.putDouble("OPERAND", mCalculatorBrain.getResult());
outState.putDouble("MEMORY", mCalculatorBrain.getMemory());
}
@Override
protected void onRestoreInstanceState(Bundle savedInstanceState) {
super.onRestoreInstanceState(savedInstanceState);
// Restore variables on screen orientation change
mCalculatorBrain.setOperand(savedInstanceState.getDouble("OPERAND"));
mCalculatorBrain.setMemory(savedInstanceState.getDouble("MEMORY"));
mCalculatorDisplay.setText(df.format(mCalculatorBrain.getResult()));
}
}CalculatorBrain.java
package example.com.calculator;
import android.content.Context;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStreamWriter;
/**
* Created by neeraj on 19-03-2016.
*/
public class CalculatorBrain {
// 3 + 6 = 9
// 3 & 6 are called the operand.
// The + is called the operator.
// 9 is the result of the operation.
private double mOperand;
private double mWaitingOperand;
private String mWaitingOperator;
private double mCalculatorMemory;
// operator types
public static final String ADD = "+";
public static final String SUBTRACT = "-";
public static final String MULTIPLY = "*";
public static final String DIVIDE = "/";
public static final String CLEAR = "C" ;
public static final String CLEARMEMORY = "MC";
public static final String ADDTOMEMORY = "M+";
public static final String SUBTRACTFROMMEMORY = "M-";
public static final String RECALLMEMORY = "MR";
public static final String SQUAREROOT = "√";
public static final String SQUARED = "x²";
public static final String INVERT = "1/x";
public static final String TOGGLESIGN = "+/-";
public static final String SINE = "sin";
public static final String COSINE = "cos";
public static final String TANGENT = "tan";
// public static final String EQUALS = "=";
// constructor
public CalculatorBrain() {
// initialize variables upon start
mOperand = 0;
mWaitingOperand = 0;
mWaitingOperator = "";
mCalculatorMemory = 0;
}
public void setOperand(double operand) {
mOperand = operand;
}
public double getResult() {
return mOperand;
}
// used on screen orientation change
public void setMemory(double calculatorMemory) {
mCalculatorMemory = calculatorMemory;
}
// used on screen orientation change
public double getMemory() {
return mCalculatorMemory;
}
public String toString() {
return Double.toString(mOperand);
}
protected double performOperation(String operator) throws IOException {
if (operator.equals(CLEAR)) {
mOperand = 0;
mWaitingOperator = "";
mWaitingOperand = 0;
// mCalculatorMemory = 0;
} else if (operator.equals(CLEARMEMORY)) {
mCalculatorMemory = 0;
} else if (operator.equals(ADDTOMEMORY)) {
mCalculatorMemory = mCalculatorMemory + mOperand;
} else if (operator.equals(SUBTRACTFROMMEMORY)) {
mCalculatorMemory = mCalculatorMemory - mOperand;
} else if (operator.equals(RECALLMEMORY)) {
mOperand = mCalculatorMemory;
} else if (operator.equals(SQUAREROOT)) {
mOperand = Math.sqrt(mOperand);
} else if (operator.equals(SQUARED)) {
mOperand = mOperand * mOperand;
} else if (operator.equals(INVERT)) {
if (mOperand != 0) {
mOperand = 1 / mOperand;
}
} else if (operator.equals(TOGGLESIGN)) {
mOperand = -mOperand;
} else if (operator.equals(SINE)) {
mOperand = Math.sin(Math.toRadians(mOperand)); // Math.toRadians(mOperand) converts result to degrees
} else if (operator.equals(COSINE)) {
mOperand = Math.cos(Math.toRadians(mOperand)); // Math.toRadians(mOperand) converts result to degrees
} else if (operator.equals(TANGENT)) {
mOperand = Math.tan(Math.toRadians(mOperand)); // Math.toRadians(mOperand) converts result to degrees
} else {
performWaitingOperation();
mWaitingOperator = operator;
mWaitingOperand = mOperand;
}
return mOperand;
}
protected void performWaitingOperation() {
if (mWaitingOperator.equals(ADD)) {
mOperand = mWaitingOperand + mOperand;
} else if (mWaitingOperator.equals(SUBTRACT)) {
mOperand = mWaitingOperand - mOperand;
} else if (mWaitingOperator.equals(MULTIPLY)) {
mOperand = mWaitingOperand * mOperand;
} else if (mWaitingOperator.equals(DIVIDE)) {
if (mOperand != 0) {
mOperand = mWaitingOperand / mOperand;
}
}
}
}activity_main.xml (in res/layout)
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/functionPad"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:layout_gravity="center"
android:orientation="vertical"
android:paddingBottom="@dimen/activity_vertical_margin"
android:paddingLeft="@dimen/activity_horizontal_margin"
android:paddingRight="@dimen/activity_horizontal_margin"
android:paddingTop="@dimen/activity_vertical_margin" >
<LinearLayout
android:id="@+id/row1"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".12" >
<TextView
android:id="@+id/textView1"
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:gravity="right"
android:maxLines="1"
android:paddingLeft="10dp"
android:paddingRight="10dp"
android:text="0"
android:textAppearance="?android:attr/textAppearanceLarge"
android:textSize="40sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/row2"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".12" >
<Button
android:id="@+id/buttonClearMemory"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonClearMemory"
android:textSize="25sp" />
<Button
android:id="@+id/buttonAddToMemory"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonAddToMemory"
android:textSize="25sp" />
<Button
android:id="@+id/buttonSubtractFromMemory"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonSubtractFromMemory"
android:textSize="25sp" />
<Button
android:id="@+id/buttonRecallMemory"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonRecallMemory"
android:textSize="25sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/row7"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".12" >
<Button
android:id="@+id/buttonSquareRoot"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonSquareRoot"
android:textSize="25sp" />
<Button
android:id="@+id/buttonSquared"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonSquared"
android:textSize="25sp" />
<Button
android:id="@+id/buttonInvert"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonInvert"
android:textSize="17sp" />
<Button
android:id="@+id/buttonSine"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonSine"
android:textSize="17sp" />
<Button
android:id="@+id/buttonCosine"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonCosine"
android:textSize="17sp" />
<Button
android:id="@+id/buttonTangent"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonTangent"
android:textSize="17sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/row3"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".12" >
<Button
android:id="@+id/buttonClear"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonClear"
android:textSize="25sp" />
<Button
android:id="@+id/buttonToggleSign"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonToggleSign"
android:textSize="25sp" />
<Button
android:id="@+id/buttonDivide"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonDivide"
android:textSize="25sp" />
<Button
android:id="@+id/buttonMultiply"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonMultiply"
android:textSize="25sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/row4"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".12" >
<Button
android:id="@+id/button7"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/button7"
android:textSize="25sp" />
<Button
android:id="@+id/button8"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/button8"
android:textSize="25sp" />
<Button
android:id="@+id/button9"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/button9"
android:textSize="25sp" />
<Button
android:id="@+id/buttonSubtract"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonSubtract"
android:textSize="25sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/row5"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".12" >
<Button
android:id="@+id/button4"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/button4"
android:textSize="25sp" />
<Button
android:id="@+id/button5"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/button5"
android:textSize="25sp" />
<Button
android:id="@+id/button6"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/button6"
android:textSize="25sp" />
<Button
android:id="@+id/buttonAdd"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonAdd"
android:textSize="25sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/row6"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".24"
android:baselineAligned="false" >
<LinearLayout
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".75"
android:orientation="vertical" >
<LinearLayout
android:id="@+id/linearLayout1"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".50"
android:textSize="25sp" >
<Button
android:id="@+id/button1"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".33"
android:text="@string/button1"
android:textSize="25sp" />
<Button
android:id="@+id/button2"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".33"
android:text="@string/button2"
android:textSize="25sp" />
<Button
android:id="@+id/button3"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".34"
android:text="@string/button3"
android:textSize="25sp" />
</LinearLayout>
<LinearLayout
android:id="@+id/linearLayout2"
android:layout_width="match_parent"
android:layout_height="0dp"
android:layout_weight=".50" >
<Button
android:id="@+id/button0"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".66"
android:text="@string/button0"
android:textSize="25sp" />
<Button
android:id="@+id/buttonDecimalPoint"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".34"
android:text="@string/buttonDecimalPoint"
android:textSize="25sp" />
</LinearLayout>
</LinearLayout>
<Button
android:id="@+id/buttonEquals"
android:layout_width="0dp"
android:layout_height="match_parent"
android:layout_weight=".25"
android:text="@string/buttonEquals"
android:textSize="25sp" />
</LinearLayout>
</LinearLayout>strings.xml (in res/values)
<?xml version="1.0" encoding="utf-8"?>
<resources>
<string name="app_name">Calculator</string>
<string name="menu_settings">Settings</string>
<string name="action_settings">Settings</string>
<string name="button0">0</string>
<string name="button1">1</string>
<string name="button2">2</string>
<string name="button3">3</string>
<string name="button4">4</string>
<string name="button5">5</string>
<string name="button6">6</string>
<string name="button7">7</string>
<string name="button8">8</string>
<string name="button9">9</string>
<string name="buttonAdd">+</string>
<string name="buttonSubtract">-</string>
<string name="buttonMultiply">*</string>
<string name="buttonDivide">/</string>
<string name="buttonToggleSign">+/-</string>
<string name="buttonDecimalPoint">.</string>
<string name="buttonEquals">=</string>
<string name="buttonClear">C</string>
<string name="buttonClearMemory">MC</string>
<string name="buttonAddToMemory">M+</string>
<string name="buttonSubtractFromMemory">M-</string>
<string name="buttonRecallMemory">MR</string>
<string name="buttonSquareRoot">√</string>
<string name="buttonSquared">x²</string>
<string name="buttonInvert">1/x</string>
<string name="buttonSine">sin</string>
<string name="buttonCosine">cos</string>
<string name="buttonTangent">tan</string>
</resources>#encryption.py
import hashlib
import sys
import os
import binascii
try:
hash_name = sys.argv[1]
except IndexError:
print('1st arg\n'+ str(hashlib.algorithms_guaranteed)+'\n2nd arg username','\n3rd arg password')
else:
try:
username = sys.argv[2]
passwd = sys.argv[3]
password = bytes(passwd,'UTF-8')
except IndexError:
print('using default password: password')
password = b'password'
salt = os.urandom(32)
chef_salt = binascii.hexlify(salt)
filename = username+"_salt.key"
salT_file = open(username+"_salt.key","w")
print("Salt\n"+chef_salt.decode('utf-8'))
salT_file.write(chef_salt.decode('utf-8'))
salT_file.close()
dk = hashlib.pbkdf2_hmac(hash_name, password, chef_salt, 100000,128)
store_hash = binascii.hexlify(dk)
filename = username+"_hash.hash"
hash_file = open(username+"_hash.hash","w")
print("hash\n"+store_hash.decode('utf-8'))
hash_file.write(store_hash.decode('utf-8'))
hash_file.close()
# verification.py
import hashlib
import sys
import os
import binascii
try:
hash_name = sys.argv[1]
except IndexError:
print('Specify the hash name as the first argument.')
else:
try:
username = sys.argv[2]
passwd = sys.argv[3]
password = bytes(passwd,'UTF-8')
except IndexError:
print('using default password: password')
password = b'password'
try:#password = bytes(passwd,'UTF-8')
salT_file = open(username+"_salt.key")
chef_salt = salT_file.read()
print("Salt\n"+chef_salt)
dk = hashlib.pbkdf2_hmac(hash_name, password, bytes(chef_salt,'UTF-8'), 100000,128)
hashk = binascii.hexlify(dk)
new_hash = hashk.decode('utf-8')
hash_file = open(username+"_hash.hash")
old_hash = hash_file.read()
print("hash\n"+old_hash)
if new_hash == old_hash:
print("The user "+username+" has used valid password")
else:
print("Incorrect username or password")
except OSError as e:
print("Incorrect username or password")
Algo
To Store a Password
1.Generate a long random salt using a CSPRNG.
2.generate hash using standard cryptographic hash function such as SHA256
3.key stretching using PBKDF2 inpust name = standard cryptographic hash function such as SHA256, password = hash generated, salt = salt, round = 10000 aleast, dklen = 64 atleast length of derived key
4.Save both the salt and the hash in the user's database record.
To Validate a Password
1.Retrieve the user's salt and hash from the database.
2.Prepend the salt to the given password and hash it using the same hash function.
3.Compare the hash of the given password with the hash from the database. If they match, the password is correct. Otherwise, the password is incorrect.
#8q.py
import json
inf=open("8q.json")
board=json.loads(inf.read())
board=board["matrix"]
for i in board:
print(i)
def issafe(row,col):
for i in range(8):
for j in range(8):
if(board[i][j]==1): #if a queen exists here, then check if it attacks our queen
if(row==i):
return False
if(col==j):
return False
if(abs(row-i)==abs(col-j)):
return False
return True
def place(col):
if(col>=8): #if all 8 queens are placed, then finish
print("\t\tCompleted...")
return True
for i in range(8): #checking for all rows in that column
if(board[i][col]==1): #if a queen is already placed here,
return place(col+1) #then simply place for next column
if(issafe(i,col)): #is it safe?
board[i][col]=1 #queen is placed here
if(place(col+1)==True): #recursive call to place next queen
return True
board[i][col]=0 #if not placed, then backtrack, i.e it sets to zero and the loop iterates to check for next position
return False
if(place(0)==True):
print("solution found")
else:
print("Solution not possible")
for i in board:
print(i)
#8q.json
{"matrix": [
[0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 0, 0]]}
1. 8 QUEENS PROBLEM USING BACK TRACKING
2. BACK TRACKING
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate ‘c’ ("backtracks") as soon as it determines that ‘c’ cannot possibly be completed to a valid solution.
Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles.
3.
It is also the basis of the so-called logic programming languages such as Planner and Prolog.
The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s.
The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility.
4.
The good example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight queens on a standard chessboard so that no queen attacks any other.
In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns.
Any partial solution that contains two mutually attacking queens can be abandoned, since it cannot possibly be completed to a valid solution
5. WHAT IS 8 QUEEN PROBLEM?
The eight queens puzzle is the problem of placing eight chess queens on an 8 8 chessboard so that no two queens attack each other.
Thus, a solution requires that no two queens share the same row, column, or diagonal.
The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n n chessboard, where solutions exist for all natural numbers n with the exception of 1, 2 and 3.
The solution possibilities are discovered only up to 23 queen.
6. PROBLEM INVENTOR
The puzzle was originally proposed in 1848 by the chess player Max Bezzel, and over the years, many mathematicians, including Gauss, have worked on this puzzle and its generalized n-queens problem.
7. SOLUTION INVENTOR
The first solution for 8 queens were provided by Franz Nauck in 1850. Nauck also extended the puzzle to n-queens problem (on an n n board—a chessboard of arbitrary size).
In 1874, S. Günther proposed a method of finding solutions by using determinants, and J.W.L. Glaisher refined this approach.
Edsger Dijkstra used this problem in 1972 to illustrate the power of what he called structured programming.
He published a highly detailed description of the development of a depth-first backtracking algorithm.
8. Formulation : States: any arrangementof 0 to 8 queens on theboard Initial state: 0 queens onthe board Successor function: adda queen in any squareGoal test: 8 queens onthe board, none attacked
9. BACKTRACKING CONCEPT
Each recursive call attempts to place a queen in a specificcolumn.
For a given call, the state of the board from previousplacements is known (i.e. where are the other queens?)
Current step backtracking: If a placement within thecolumn does not lead to a solution, the queen is removed andmoved "down" the column
Previous step backtracking: When all rows in a columnhave been tried, the call terminates and backtracks to theprevious call (in the previous column)
10. CONTINU..Pruning: If a queen cannot be placed into column i, do noteven try to place one onto column i+1 – rather, backtrack to column i-1 and move the queen that had beenplaced there.Using this approach we can reduce the number of potentialsolutions even more
11. BACKTRACKING DEMO FOR 4 QUEENS
12. STEPS REVISITED - BACKTRACKING1. Place the first queen in the left upper corner of the table.2. Save the attacked positions.3. Move to the next queen (which can only be placed to the next line).4. Search for a valid position. If there is one go to step 8.5. There is not a valid position for the queen. Delete it (the x coordinate is 0).6. Move to the previous queen.7. Go to step 4.8. Place it to the first valid position.9. Save the attacked positions.10. If the queen processed is the last stop otherwise go to step 3.
13. EIGHT QUEEN PROBLEM: ALGORITHMputQueen(row){ for every position col on the same row if position col is available place the next queen in position col if (row<8) putQueen(row+1); else success; remove the queen from position col}
14. THE PUTQUEEN RECURSIVE METHODvoid putQueen(int row) { for (int col=0;col<squares;col++) if (column[col]==available && leftDiagonal[row+col]==available && rightDiagonal[row-col]== available) { positionInRow[row]=col; column[col]=!available; leftDiagonal[row+col]=!available;
15. rightDiagonal[row-col]=!available; if (row< squares-1) putQueen(row+1); else print(" solution found”); column[col]=available; leftDiagonal[row+col]=available; rightDiagonal[row-col]= available; }}
16. SOLUTIONS• The eight queens puzzle has 92 distinct solutions.• If solutions that differ only by symmetry operations(rotations and reflections) of the board are counted as one the puzzle has 12 unique (or fundamental) solutions
17. COUNTING SOLUTIONS
The following table gives the number of solutions for placing n queens on an n n board, both unique and distinct for n=1–26.
Note that the six queens puzzle has fewer solutions than the five queens puzzle.
There is currently no known formula for the exact number of solutions.
18. Order(“N”) Total Solutions Unique Solutions Exec time---------------------------------------------------------1 1 1 < 0 seconds2 0 0 < 0 seconds3 0 0 < 0 seconds4 2 1 < 0 seconds5 10 2 < 0 seconds6 4 1 < 0 seconds7 40 6 < 0 seconds8 92 12 < 0 seconds9 352 46 < 0 seconds10 724 92 < 0 seconds11 2,680 341 < 0 seconds12 14,200 1,787 < 0 seconds13 73,712 9,233 < 0 seconds14 365,596 45,752 0.2s
19. 15 2,279,184 285,053 1.9 s16 14,772,512 1,846,955 11.2 s17 95,815,104 11,977,939 77.2 s18 666,090,624 83,263,591 9.6 m19 4,968,057,848 621,012,754 75.0 m20 39,029,188,884 4,878,666,808 10.2 h21 314,666,222,712 39,333,324,973 87.2 h22 2,691,008,701,644 336,376,244,042 31.923 24,233,937,684,440 3,029,242,658,210 296 d24 227,514,171,973,736 28,439,272,956,934 ?25 2,207,893,435,808,352 275,986,683,743,434 ?26 22,317,699,616,364,044 2,789,712,466,510,289 ? (s = seconds m = minutes h = hours d = days)
20. JEFF SOMER’S ALGORITHM
His algorithm for the N-Queen problem is considered as the fastest algorithm. He uses the concept of back tracking to solve this
Previously the World’s fastest algorithm for the N-Queen problem was given by Sylvain Pion and Joel-Yann Fourre.
His algorithm finds solutions up to 23 queens and uses bit field manipulation in BACKTRACKING.
According to his program the maximum time taken to find all the solutions for a 18 queens problem is 00:19:26 where as in the normal back tracking algorithm it was 00:75:00.
21. USING NESTED LOOPS FOR SOLUTIONFor a 4x4 board, we could find the solutions like this: for(i0 = 0; i0 < 4; ++i0) { if(isSafe(board, 0, i0)) { board[0][i0] = true; for(i1 = 0; i1 < 4; ++i1) { if(isSafe(board, 1, i1)) { board[1][i1] = true; for(i2 = 0; i2 < 4; ++i2) { if(isSafe(board 2, i2)) { board[2][i2] = true; for(i3 = 0; i3 < 4; ++i3) { if(isSafe(board 3, i3)) { board[3][i3] = true;
22. { printBoard(board, 4);} board[3][i3] = false; } } board[2][i2] = false; } } board[1][i1] = false; } } board[0][i0] = false; } }
23. WHY NOT NESTED LOOP
The nested loops are not so preferred because . It Does not scale to different sized boards
You must duplicate identical code (place and remove). and error in one spot is hard to find
The problem with this is that its not very programmer- friendly. We cant vary at runtime the size of the board were searching
24.
The major advantage of the backtracking algorithm is the abillity to find and count all the possible solutions rather than just one while offering decent speed.
If we go through the algorithm for 8 queens 981 queen moves (876 position tests plus 105 backtracks) are required for the first solution alone. 16,704 moves (14,852 tests and 1852 backtracks) are needed to find all 92 solutions.
Given those figures, its easy to see why the solution is best left to computers.
//index.jsp
<%--
Document : index
Created on : 9 Mar, 2016, 11:06:22 AM
Author :
--%>
<%@page contentType="text/html" pageEncoding="UTF-8"%>
<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>JSP Page</title>
</head>
<body>
<form action="Plagarism">
Enter the first input <textarea name="File1" rows="5" cols="10">
</textarea><br>
Enter the second input<textarea name="File2" rows="5" cols="10">
</textarea><br>
<input type="submit" value="Check Plagarism" name="btn"/>
</form>
</body>
</html>
//Plagarism.java
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
import java.io.IOException;
import java.io.PrintWriter;
import javax.servlet.ServletException;
import javax.servlet.annotation.WebServlet;
import javax.servlet.http.HttpServlet;
import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
/**
*
* @author
*/
@WebServlet(urlPatterns = {"/Plagarism"})
public class Plagarism extends HttpServlet {
/**
* Processes requests for both HTTP <code>GET</code> and <code>POST</code>
* methods.
*
* @param request servlet request
* @param response servlet response
* @throws ServletException if a servlet-specific error occurs
* @throws IOException if an I/O error occurs
*/
protected void processRequest(HttpServletRequest request, HttpServletResponse response)
throws ServletException, IOException {
response.setContentType("text/html;charset=UTF-8");
PrintWriter out = response.getWriter();
try {
out.println("<!DOCTYPE html>");
out.println("<html>");
out.println("<head>");
out.println("<title>Servlet Plagarism</title>");
out.println("</head>");
out.println("<body>");
String fileOne = request.getParameter("File1");
String fileTwo = request.getParameter("File2");
out.println("Comparing the 2 files......");out.println("<br>");
String[] str1 = fileOne.split("\\s");
String[] str2 = fileTwo.split("\\s");
for (int j = 0; j < str1.length; j++) { //alphabetical order sorting of str1
for (int i = j + 1; i < str1.length; i++) {
if (str1[i].compareTo(str1[j]) < 0) {
String t = str1[j];
str1[j] = str1[i];
str1[i] = t;
}
}
}
int results; double plag=0;
for (int key = 0; key < str2.length; key++){
results = searchString(str1, str2[key]);
if (results == 1) {
plag = plag+1;
}
}
double plagPercent = (plag/str2.length)*100;
out.println("Similarity between two text is "+ plagPercent);
out.println("<br>");
out.println("Plagrism "+((plagPercent>50.0) ? "exist" : "does not exist"));
out.println("</body>");
out.println("</html>");
} finally {
out.close();
}
}
//simple binary search
public static int searchString(String[] str1, String key) {
int first = 0;
int last = str1.length;
while (first < last) {
int mid = (first + last) / 2;
if (key.compareTo(str1[mid]) < 0) {
last = mid;
} else if (key.compareTo(str1[mid]) > 0) {
first = mid + 1;
} else {
return 1;
}
}
return -1;
}
// <editor-fold defaultstate="collapsed" desc="HttpServlet methods. Click on the + sign on the left to edit the code.">
/**
* Handles the HTTP <code>GET</code> method.
*
* @param request servlet request
* @param response servlet response
* @throws ServletException if a servlet-specific error occurs
* @throws IOException if an I/O error occurs
*/
@Override
protected void doGet(HttpServletRequest request, HttpServletResponse response)
throws ServletException, IOException {
processRequest(request, response);
}
/**
* Handles the HTTP <code>POST</code> method.
*
* @param request servlet request
* @param response servlet response
* @throws ServletException if a servlet-specific error occurs
* @throws IOException if an I/O error occurs
*/
@Override
protected void doPost(HttpServletRequest request, HttpServletResponse response)
throws ServletException, IOException {
processRequest(request, response);
}
/**
* Returns a short description of the servlet.
*
* @return a String containing servlet description
*/
@Override
public String getServletInfo() {
return "Short description";
}// </editor-fold>
}
//test.java
import org.openqa.selenium.By;
import org.openqa.selenium.WebDriver;
import org.openqa.selenium.WebElement;
import org.openqa.selenium.firefox.FirefoxDriver;
public class mytest3
{
public static void main(String[] args) {
WebDriver driver = new FirefoxDriver();
String baseUrl = "http://localhost:8084/plagraism/";
driver.get(baseUrl);
String expected = "JSP Page";
String actual = "";
driver.manage().window().maximize();
actual = driver.getTitle();
if (actual.equals(expected)) {
System.out.println("Title test passed");
} else {
System.out.println("Title test failed");}
WebElement text=driver.findElement(By.name("File1"));
text.sendKeys("hello");
WebElement text1=driver.findElement(By.name("File2"));
text1.sendKeys("hiee");
WebElement btn=driver.findElement(By.name("btn"));
btn.click();
System.out.println(" test script sucessful");
driver.close();
}
}
#sha1.py
def sha1(data):
bytes = ""
h0 = 0x67452301 # Initialize variables
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
for n in range(len(data)):
bytes+='{0:08b}'.format(ord(data[n]))
bits = bytes+"1"
pBits = bits
#pad until length equals 448 mod 512
while len(pBits)%512 != 448:
pBits+="0"
#append the original length
pBits+='{0:064b}'.format(len(bits)-1)
def chunks(l, n):
return [l[i:i+n] for i in range(0, len(l), n)]
def rol(n, b):
return ((n << b) | (n >> (32 - b))) & 0xffffffff
for c in chunks(pBits, 512):
words = chunks(c, 32)
w = [0]*80
for n in range(0, 16):
w[n] = int(words[n], 2)
for i in range(16, 80):
w[i] = rol((w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]), 1)
a = h0
b = h1
c = h2
d = h3
e = h4
#Main loop
for i in range(0, 80):
if 0 <= i <= 19:
#f = (b & c) | ((~b) & d)
f = b ^ c ^ d
k = 0x5A827999
elif 20 <= i <= 39:
f = b ^ c ^ d
k = 0x6ED9EBA1
elif 40 <= i <= 59:
#f = (b & c) | (b & d) | (c & d)
f = b ^ c ^ d
k = 0x8F1BBCDC
elif 60 <= i <= 79:
#f = b ^ c ^ d
f = b ^ c ^ d
k = 0xCA62C1D6
temp = rol(a, 5) + f + e + k + w[i] & 0xffffffff
e = d
d = c
c = rol(b, 30)
b = a
a = temp
h0 = h0 + a & 0xffffffff
h1 = h1 + b & 0xffffffff
h2 = h2 + c & 0xffffffff
h3 = h3 + d & 0xffffffff
h4 = h4 + e & 0xffffffff
return '%08x%08x%08x%08x%08x' % (h0, h1, h2, h3, h4)
#print(sha1("hello"))
#server.py
import socket
import sha1
ss = socket.socket(socket.AF_INET, socket.SOCK_STREAM,0)
ss.bind(("", 5008))
ss.listen(5)
print "TCPServer1 Waiting for client on port 7998"
while 1:
client_socket, address = ss.accept()
print "I got a connection from ", address
stri = client_socket.recv(1024)
alist = stri.split('\n')
print alist[0]
checkHash=sha1.sha1(str(alist[0]))
print checkHash
if checkHash == alist[1]:
print "Message is valid"
client_socket.send("Message is Verified")
else:
client_socket.send("Message could not be verified")
client_socket.close()
ss.close()
print "Data sent!"
break;
'''
cipher@blackfury-HP-eNVy:~/be-2/BE1$ python server.py
TCPServer1 Waiting for client on port 7998
I got a connection from ('127.0.0.1', 44144)
Hello World!
2b72790bf888c4427287b3d79a8c8a3320c61986
Message is valid
Data sent!
'''
#client.py
# TCP client example
import socket
import sha1
TCP_IP = '127.0.0.1'
TCP_PORT = 5008
BUFFER_SIZE = 1024
MESSAGE = raw_input("Enter a message: ")
digest = sha1.sha1(MESSAGE)
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((TCP_IP, TCP_PORT))
s.send(MESSAGE+"\n")#could directly use s.send(MESSAGE+"\n"+digest) i dont know why but someone told me...
s.send(digest)#could comment this.
data = s.recv(BUFFER_SIZE)
s.close()
print "received data:", data
Note 1: All variables are unsigned 32-bit quantities and wrap modulo 232 when calculating, except for
ml, the message length, which is a 64-bit quantity, and
hh, the message digest, which is a 160-bit quantity.
Note 2: All constants in this pseudo code are in big endian.
Within each word, the most significant byte is stored in the leftmost byte position
Initialize variables:
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
ml = message length in bits (always a multiple of the number of bits in a character).
Pre-processing:
append the bit '1' to the message e.g. by adding 0x80 if message length is a multiple of 8 bits.
append 0 ≤ k < 512 bits '0', such that the resulting message length in bits
is congruent to −64 ≡ 448 (mod 512)
append ml, in a 64-bit big-endian integer. Thus, the total length is a multiple of 512 bits.
Process the message in successive 512-bit chunks:
break message into 512-bit chunks
for each chunk
break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15
Extend the sixteen 32-bit words into eighty 32-bit words:
for i from 16 to 79
w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1
Initialize hash value for this chunk:
a = h0
b = h1
c = h2
d = h3
e = h4
Main loop:[44][2]
for i from 0 to 79
if 0 ≤ i ≤ 19 then
f = (b and c) or ((not b) and d)
k = 0x5A827999
else if 20 ≤ i ≤ 39
f = b xor c xor d
k = 0x6ED9EBA1
else if 40 ≤ i ≤ 59
f = (b and c) or (b and d) or (c and d)
k = 0x8F1BBCDC
else if 60 ≤ i ≤ 79
f = b xor c xor d
k = 0xCA62C1D6
temp = (a leftrotate 5) + f + e + k + w[i]
e = d
d = c
c = b leftrotate 30
b = a
a = temp
Add this chunk's hash to result so far:
h0 = h0 + a
h1 = h1 + b
h2 = h2 + c
h3 = h3 + d
h4 = h4 + e
Produce the final hash value (big-endian) as a 160 bit number:
hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4
The number hh is the message digest, which can be written in hexadecimal (base 16), but is often written using Base64 binary to ASCII text encoding.
The constant values used are chosen to be nothing up my sleeve numbers: the four round constants k are 230 times the square roots of 2, 3, 5 and 10. The first four starting values for h0 through h3 are the same with the MD5 algorithm, and the fifth (for h4) is similar.
#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Based on the pseudocode in https://en.wikipedia.org/wiki/Mersenne_Twister.
Generates uniformly distributed 32-bit integers in the range [0, 232 − 1] with the MT19937 algorithm
"""
# Create a length 624 list to store the state of the generator
MT = [0 for i in xrange(624)]
index = 0
# To get last 32 bits
bitmask_1 = (2 ** 32) - 1
# To get 32. bit
bitmask_2 = 2 ** 31
# To get last 31 bits
bitmask_3 = (2 ** 31) - 1
def initialize_generator(seed):
"Initialize the generator from a seed"
global MT
global bitmask_1
MT[0] = seed
for i in xrange(1,624):
MT[i] = ((1812433253 * MT[i-1]) ^ ((MT[i-1] >> 30) + i)) & bitmask_1
def extract_number():
"""
Extract a tempered pseudorandom number based on the index-th value,
calling generate_numbers() every 624 numbers
"""
global index
global MT
if index == 0:
generate_numbers()
y = MT[index]
y ^= y >> 11
y ^= (y << 7) & 2636928640
y ^= (y << 15) & 4022730752
y ^= y >> 18
index = (index + 1) % 624
return y
def generate_numbers():
"Generate an array of 624 untempered numbers"
global MT
for i in xrange(624):
y = (MT[i] & bitmask_2) + (MT[(i + 1 ) % 624] & bitmask_3)
MT[i] = MT[(i + 397) % 624] ^ (y >> 1)
if y % 2 != 0:
MT[i] ^= 2567483615
if __name__ == "__main__":
from datetime import datetime
now = datetime.now()
initialize_generator(now.microsecond)
for i in xrange(5):
"Print 5 random numbers as an example"
print extract_number()
// Create a length n array to store the state of the generator
int[0..n-1] MT
int index := n+1
const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
const int upper_mask = lowest w bits of (not lower_mask)
// Initialize the generator from a seed
function seed_mt(int seed) {
index := n
MT[0] := seed
for i from 1 to (n - 1) { // loop over each element
MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
}
}
// Extract a tempered value based on MT[index]
// calling twist() every n numbers
function extract_number() {
if index >= n {
if index > n {
error "Generator was never seeded"
// Alternatively, seed with constant value; 5489 is used in reference C code[44]
}
twist()
}
int y := MT[index]
y := y xor ((y >> u) and d)
y := y xor ((y << s) and b)
y := y xor ((y << t) and c)
y := y xor (y >> l)
index := index + 1
return lowest w bits of (y)
}
// Generate the next n values from the series x_i
function twist() {
for i from 0 to (n-1) {
int x := (MT[i] and upper_mask)
+ (MT[(i+1) mod n] and lower_mask)
int xA := x >> 1
if (x mod 2) != 0 { // lowest bit of x is 1
xA := xA xor a
}
MT[i] := MT[(i + m) mod n] xor xA
}
index := 0
}
import java.awt.Container;
import java.awt.TextArea;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JTextArea;
import javax.swing.JTextField;
public class IDS1 {
public static String line;
public static JFrame fr;
public static Container c;
public static JTextArea tx;
public static JScrollPane js;
public static JButton ids_on,ids_off,disp_blocked_ip,disp_rules,unblock_ip;
public static JTextField ip;
public IDS1(){
fr=new JFrame();
c=fr.getContentPane();
c.setLayout(null);
fr.setTitle("Intrusion Detection System Config");
fr.setBounds(0, 0, 920, 550);
//components on the frame
tx=new JTextArea();
js=new JScrollPane(tx,JScrollPane.VERTICAL_SCROLLBAR_ALWAYS,JScrollPane.HORIZONTAL_SCROLLBAR_ALWAYS);
ids_on=new JButton("IDS ON");
ids_off=new JButton("IDS OFF");
disp_blocked_ip=new JButton("Blocked IPs");
disp_rules=new JButton("Firewall Rules");
ip=new JTextField("Enter Ip address");
unblock_ip=new JButton("Unblock Ip");
//setting bounds
js.setBounds(5, 20, 900, 400);
ids_on.setBounds(10, 470, 120, 50);
ids_off.setBounds(10, 470, 120, 50);
disp_blocked_ip.setBounds(140, 470, 120, 50);
disp_rules.setBounds(270, 470, 120, 50);
unblock_ip.setBounds(410, 470, 120, 50);
ip.setBounds(410, 520, 220, 50);
ip.setVisible(false);
//adding components on the frame container
c.add(js);
c.add(ids_on);
c.add(ids_off);
c.add(disp_blocked_ip);
c.add(unblock_ip);
c.add(ip);
c.add(disp_rules);
//all button's action listeners
ids_on.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
ids_on.setVisible(false);
ids_off.setVisible(true);
exec_commands("sudo service psad start");
exec_commands("sudo service psad status");
}
});
ids_off.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
ids_on.setVisible(true);
ids_off.setVisible(false);
exec_commands("sudo service psad stop");
exec_commands("sudo service psad status");
}
});
disp_blocked_ip.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
exec_commands("sudo iptables -L INPUT -v -n --line-numbers");
}
});
disp_rules.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
//exec_commands("sudo iptables -N TRAFFIC_ACCT");//own traffic chain in order to avoid changes in firewall rules
//exec_commands("sudo iptables -I FORWARD -j TRAFFIC_ACCT");//forwarding all traffic to my created chain
//exec_commands("iptables -A TRAFFIC_ACCT -p tcp && iptables -A TRAFFIC_ACCT -p ip && iptables -A TRAFFIC_ACCT -p icmp");
exec_commands("sudo iptables -L");
}
});
unblock_ip.addActionListener(new ActionListener() {
@Override
public void actionPerformed(ActionEvent arg0) {
String response = JOptionPane.showInputDialog(null,"Enter IP address",
JOptionPane.QUESTION_MESSAGE);
exec_commands("sudo iptables -D INPUT -s "+response+" -j DROP");
}
});
fr.setVisible(true);
fr.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
//Main method
public static void main(String arr[]) throws Exception{
IDS1 ids=new IDS1();
}
//method for execute the commands
public void exec_commands(String cmd){
try {
Runtime rt = Runtime.getRuntime();
//Process pr = rt.exec("cmd /c dir");
Process pr = rt.exec(cmd);
BufferedReader input = new BufferedReader(new InputStreamReader(pr.getInputStream()));
String line=null;
tx.setText("");
while((line=input.readLine()) != null) {
System.out.println(line);
//display cmd output on textarea tx
tx.append(line+"\n");
}
//int exitVal = pr.waitFor();
// System.out.println("Exited with error code "+exitVal);
} catch(Exception e) {
System.out.println(e.toString());
e.printStackTrace();
}
}
}
https://www.digitalocean.com/community/tutorials/how-to-use-psad-to-detect-network-intrusion-attempts-on-an-ubuntu-vps
sudo /sbin/iptables -A INPUT -s 65.55.44.102 -j DROP ---------------add ip address to be blocked
sudo apt-get install psad
sudo iptables -A INPUT -j LOG ---------------------------For logging purpose(optional)
sudo iptables -A FORWARD -j LOG--------------------------
sudo iptables -F ---------------Flush rules
sudo iptables -L ---------------List all rules
sudo iptables -A INPUT -m conntrack --ctstate ESTABLISHED,RELATED -j ACCEPT --------------------- explicitly allow all traffic related to
an existing connection.
sudo iptables -A INPUT -p tcp --dport 22 -j ACCEPT ---------------------services that we wish to keep open to the public
sudo iptables -A INPUT -j LOG
sudo iptables -A FORWARD -j LOG
sudo iptables -P INPUT DROP ------------------DROP all extraneous messages
sudo apt-get install iptables-persistent ------------------- makes these rules persistent(optional)
sudo service iptables-persistent start(opyional)
sudo gedit /etc/psad/psad.conf -----open and change e-mail address to your email or any other and can also change the domain as per your need
sudo psad --sig-update -------------------Update the signatures of the definitions of the known attacks
sudo service psad restart --------------Restart the psad IDS
-----------end-------------