Софтуерно Инженерство
Loading...
+ Нов въпрос
rsmarinoff avatar rsmarinoff 49 Точки

Лекция 6 - Домашно - Задача 2

Първоначално задачата не ми направи впечатление, тъй като решението изглеждаше сравнително лесно, но после ударих на камък. За да сметна някакъв триъгълник ми трябват операции с плаваща точка, от рода на корени, тригонометрия и т.н. Ядрото (очаквано) не харесва особено операциите с плаваща точка по ред причини, които не са важни в случая, затова и няма кой знае какви библиотеки за тях, поне аз не можах да намеря, а по форумите като цяло се карат на всеки, който пита за fp аритметика и се чудят за какво му е. laugh Тук се сетих за два варианта да заобиколя въпросния проблем:

Самата floating point аритметика може да бъде пусната за x86 архитектури по следния начин:

#include <asm/i387.h>

int some_function(void){
    kernel_fpu_begin();
// Do some calculations or whatever...
    kernel_fpu_end();
    return 0;
}

 Програмата ще използва копроцесора за аритметика с плаваща запетая и ще направи каквото трябва. Между другото, имаше и някакъв друг хедър, който емулираше тази аритметика софтуерно, така че и той остава вариант, както и да е. Това означава, обаче, да си пиша сам функцията за корен квадратен, което не е чак такъв проблем. Тригонометрията вероятно ще е голям зор, ако въобще е възможно да се напише без inline assembly в нея. Отново, леко задънена улица, или поне нещо, което предпочитам да избегна.

Вторият вариант е да използвам inline assembly и по подобен начин на горния да си направя сметките с x87 инструкциите, където има и корен квадратен, и тригонометрия. Назад съм с асемблера, но, като цяло, приемлив вариант. Тук, обаче, също удрям на камък, защото не мога да намеря функция, която ще изпринти floating point стойност в proc файл. seq_printf() отказва упорито.

С това се изчерпва моят опит до момента, споделете и вашия, ако искате, разбира се.

1
Linux Курсове 08/02/2016 01:31:00
vladiant avatar vladiant 38 Точки
Best Answer

За лице на триъгълник не ти трябва плаваща запетая. Подсказка - vector cross product.

1
08/02/2016 15:58:35
rsmarinoff avatar rsmarinoff 49 Точки

Според мен, за да сметнеш лицето с вектори, пак ти трябва корен квадратен, за което ти трябва плаваща запетая. Обикновено не съм прав за такива работи, така че кажи ако пропускам нещо. laugh

0
vladiant avatar vladiant 38 Точки

Единственото, което мога да ти кажа, е да се запознаеш с дефиницията на cross product, или векторно произведение, която е добре описана в Интернет. Сравни я с формулата за лице на триъгълник.

0
rsmarinoff avatar rsmarinoff 49 Точки

Благодаря за отговорите, добре ме насочи. yes Ще видим докъде ще го докарам laugh

0
vladiant avatar vladiant 38 Точки

За square root:
http://www.codecodex.com/wiki/Calculate_an_integer_square_root

Arctan:

http://www.romanblack.com/integer_degree.htm

2
08/02/2016 16:21:58
todorstz avatar todorstz 0 Точки

Благодаря много за линковете! ;)

0
vladiant avatar vladiant 38 Точки

И да споделя малко опит. Може да се шокирате, но е напълно възможно един и същ бинарен код на различни машини да даде различни резултати при пресмятания с плаваща запетая. Разликите започват от LSB и може напълно да обезсмислят резултата в зависимост от типа на пресмятането. Затова е желателно максимално да избягвате пресмятания с плаваща запетая - още повече, че са и по-бавни. За справка:

http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

Още информация:

http://javarevisited.blogspot.bg/2014/05/10-articles-every-programmer-must-read.html

1
rsmarinoff avatar rsmarinoff 49 Точки

Мога да добавя малко лош опит. Продължих да се лигавя с floating point аритметика, въпреки добрата си преценка. Нещата работят, но само донякъде. Освен, че асемблерските инструкции ограничават до използването на определена архитектура, но и както е споменато горе, floating point аритметиката може да доведе до undefined behavior. Описал съм всичко в коментарите на постнатия код, но като цяло наистина се случват някои странни работи. Примерно, когато извикам функцията sqroot върху някой литерал и всичко е наред. Викна ли я обаче върху някакъв друг тип, дори и кастнат към float, всичко приключва и компилаторът хвърля warning за undefined behavior и модулът не се зарежда, или прави segmentation fault-ове и други подобни глупости. За това намерих workaround, като написах функция за преобразуване на int в някаква форма на float. Когато викна sqroot върху някакъв сбор от променливи, се случва нещо подобно и т.н. Като цяло не си заслужава мъките и писането на откровени простотии, затова отивам да си смятам векторите. Поствам кода кат предупреждение за ентусиасти като мен. laugh

/*
 * This one is just for kicks and it kinda demonstrates
 * why you shoudln't use floating point arithmetic in
 * a kernel module. It basically results in A LOT of
 * undefined behaviour, for which there is probably
 * a workaround but it's not worth the psychological
 * disorders on might develop looking for it.
 * Kernel modules rarely ever need to use fp arithmetic
 * in general anyway. WARNING! This will crash, if you load it
 * ... badly. So, use at your own risk
 */

#include <linux/module.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <asm/i387.h>

/***Typedefs prototypes, etc.***/
/*
 * This union is used to convert floats
 * into some form of int representation
 * so that they may later be printed,
 * since the print functions don't support
 * the %f format specifier.
 * Suffice to say, not my best idea as of
 * yet.
*/
typedef union{
	float f;
	struct{
		unsigned int mantisa : 23;
		unsigned int exponent : 8;
		unsigned int sign : 1;
	}parts;
}NEWFLOAT;

/*
 * Printable version of a float number.
 * I use this one to print the actual
 * floats after converting them from the
 * NEWFLOAT type.
 */
typedef struct{
	char sign;
	unsigned int exponent;
	unsigned int mantisa;
}PRINTFLOAT;

int power(int, int);
NEWFLOAT intToFloat(int);
PRINTFLOAT convertFloat(NEWFLOAT number);
static float sqroot(float);
float sin(float);
float cos(float);
/*******Global variables*******/
static NEWFLOAT side1, side2, side3;
static PRINTFLOAT a, b, c;
static int x1, x2, x3, y1, y2, y3;
module_param(x1, int, 0);
module_param(x2, int, 0);
module_param(x3, int, 0);
module_param(y1, int, 0);
module_param(y2, int, 0);
module_param(y3, int, 0);
/*
 * Converts an integer value
 * into a NEWFLOAT value. I
 * wrote this, because casting
 * an int to float and passing it
 * to one of the trig functions below
 * resulted in a lot of undefind behavior.
 * This is actually a passable workaround
 * for the issue.
 */
NEWFLOAT intToFloat(int arg){
	NEWFLOAT returnValue;
	unsigned int localArg = 0;
	unsigned int mask = 0x80000000;
	int i = 0;
	if(arg < 0){
		localArg |= -1*arg;
		returnValue.parts.sign = 1;
	}else{
		localArg |= arg;
		returnValue.parts.sign = 0;
	}
	for(i=32;i>0;i--){
		if((localArg & mask) != 0){
			break;
		}
		mask >>=1;
	}
	returnValue.parts.mantisa = (localArg & (~mask));
	returnValue.parts.mantisa <<= 24-i;
	returnValue.parts.exponent = i + 126;
	return returnValue;
}
/*
 * Uses the x87 sqrt instruction to get
 * the square root of a float value.
 * Calling this on the sum of two floats
 * resulted in undefined behavior at
 * which point I called it quits.
 */
static float sqroot(float arg){
	float localArg = arg;
	float returnValue;
	asm(
		"fld %1\n;"
		"fsqrt\n;"
		"fst %0;"
	:"=m"(returnValue)
	: "m"(localArg)
	);
	return returnValue;
}

/*
 * Same as above, only for sine.
 */
float sin(float arg){
	float returnValue;
	asm(
		"fld %1\n;"
		"fsin\n;"
		"fst %0;"
		:"=m"(returnValue)
		: "m"(arg)
	);
	return returnValue;
}

/*
 * Same as above, only for cosine.
 */
float cos(float arg){
	float returnValue;
	asm(
		"fld %1\n;"
		"fcos\n;"
		"fst %0;"
		:"=m"(returnValue)
		:"m"(arg)
	);
	return returnValue;
}

/*
 * Converts the NEWFLOAT union int a
 * format ready for printing. Basically
 * calculates the decimal values of the
 * exponent and mantissa from the IEE
 * float format.
 */
PRINTFLOAT convertFloat(NEWFLOAT number){
	int i=0;
	unsigned int increment = 500000;
	unsigned int mask = 0x00400000;
	unsigned int result = 1000000;
	unsigned int afterBias = 0;
	PRINTFLOAT returnValue;
	for(i=0;i<23;i++){
		if((number.parts.mantisa & mask) !=0){
			result += increment;
		}
		increment /= 2;
		mask >>= 1;
	}
	if(number.parts.exponent < 127){
		afterBias = 127 - number.parts.exponent;
		result /= power(2, afterBias);
	}else{
		afterBias = number.parts.exponent - 127;
		result*=power(2, afterBias);
	}

	if(number.parts.sign !=0){
		returnValue.sign = '-';
	}else{
		returnValue.sign = ' ';
	}
	returnValue.exponent = result/1000000;
	returnValue.mantisa = result%1000000;
	return returnValue;
}

/*
 * Power function, pretty
 * self-explanatory.
 */
int power(int number, int power){

	int result = 1;
	int i = 0;
	for(i=0;i<power;i++){
		result *= number;
	}
	return result;
}

static int hello_proc_show(struct seq_file *m, void *v) {
	seq_printf(m, "Side a: %c\n%u\n%u\n", a.sign, a.exponent, a.mantisa);
 	seq_printf(m, "Side b:%c%u.%u\n", b.sign, b.exponent, b.mantisa);
	seq_printf(m, "Side c:%c%u.%u\n", c.sign, c.exponent, c.mantisa);
  	return 0;
}

static int hello_proc_open(struct inode *inode, struct  file *file) {
  	return single_open(file, hello_proc_show, NULL);
}

static const struct file_operations hello_proc_fops = {
	.owner = THIS_MODULE,
  	.open = hello_proc_open,
  	.read = seq_read,
  	.llseek = seq_lseek,
  	.release = single_release,
};

static int __init hello_proc_init(void) {
  	kernel_fpu_begin();
	NEWFLOAT foo = intToFloat(power(x2-x1, 2));
	NEWFLOAT bar = intToFloat(power(y2-y1, 2));
	NEWFLOAT thingy;
	thingy.f = foo.f + bar.f;
	side1.f = sqroot(thingy.f);
	a = convertFloat(side1);
	side2.f = sqroot(power(x3-x2, 2)+power(y3-y2, 2));
	side3.f = sqroot(power(x1-x3, 2)+power(y1-y3, 2));
	a = convertFloat(side1);
	b = convertFloat(side2);
	c = convertFloat(side3);
	kernel_fpu_end();
  	proc_create("hello_proc", 0, NULL, &hello_proc_fops);
  	return 0;
}

static void __exit hello_proc_exit(void) {
  	remove_proc_entry("hello_proc", NULL);
}

MODULE_LICENSE("GPL");
module_init(hello_proc_init);
module_exit(hello_proc_exit);

 

1
09/02/2016 23:05:39
vladiant avatar vladiant 38 Точки

Благодаря за кода и информацията. За сведение - в MM Solutions само на няколко човека е разрешено да пишат на асемблер за нуждите на клиентите.

0
rsmarinoff avatar rsmarinoff 49 Точки

Асемблерът е нещо много хубаво, но поставя някои ограничения. Като, цяло, ако си напред с математиката можеш да пишеш много оптимален код, което е в пъти по-добре от C компилатор с набичена на макс оптимизация в който и да е случай. Уловката идва тогава, когато проектът е голям и трябва да пише повече от един човек и се стигне до разпъване и рисуване по чаршафи, спане на работа и т.н. Не е за общи цели.

0
ipenev avatar ipenev 21 Точки

В 4.4.1 ядрото няма i387.h.
Възможно е да се направи изчисление като числата се представят във форма IEEE 754

https://en.wikipedia.org/wiki/IEEE_floating_point

Но цялото това упражнение да смяташ триъгълник с модул на ядрото е безумно!

2
vladiant avatar vladiant 38 Точки

Съгласен съм. Но благодарение на него човек разбира, че при програмирането на кернел модули има много неща, които не могат да се правят както сме свикнали.

1