Update

8 files changed, 198 insertions, 112 deletions

diff --git a/Semestr 4/aisd/pracownia4/rozw.cpp b/Semestr 4/aisd/pracownia4/rozw.cpp
new file mode 100644
index 0000000..b3f97c8
--- /dev/null
+++ b/Semestr 4/aisd/pracownia4/rozw.cpp
@@ -0,0 +1,121 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+const int M = (1<<20);
+const size_t size = M*2 + 10;
+
+struct query {
+    char type;
+    union {
+        struct insert {
+            int p;
+            int x;
+        } insert;
+        struct sum {
+            int from;
+            int to;
+        } sum;
+        int del;
+    };
+};
+
+struct segtreePS {
+    int tree[size];
+
+    segtreePS() {
+        for (int i = 0; i < size; i++) tree[i] = 0;
+    }
+
+    void update(int where, int val) {
+        where += M;
+        while (where) {
+            tree[where] += val;
+            where /= 2;
+        }
+    }
+
+    int query(int from, int to) {
+        from += M;
+        to += M;
+        int ans = tree[from];
+        if (from != to) ans += tree[to];
+        while (from/2 != to/2) {
+            if (from % 2 == 0)  ans += tree[from + 1];
+            if (to % 2 == 1)    ans += tree[to - 1];
+            to /= 2; from /= 2;
+        }
+        return ans;
+    }
+};
+
+struct segtreeSP {
+    int tree[size];
+
+    segtreeSP() {
+        for (int i = 0; i < size; i++) tree[i] = 0;
+    }
+
+    void update(int from, int to, int val) {
+        from += M;
+        to += M;
+        tree[from] += val;
+        if (from != val) tree[to] += val;
+        while (from/2 != to/2) {
+            if (from % 2 == 0)  tree[from + 1] += val;
+            if (to % 2 == 1)    tree[to - 1] += val;
+            to /= 2; from /= 2;
+        }
+    }
+
+    int query(int where) {
+        int ans = 0;
+        where += M;
+        while (where) {
+            ans += tree[where];
+            where /= 2;
+        }
+        return ans;
+    }
+};
+
+vector<query> queries;
+segtreeSP sptree;
+map<int, int> q_to_pos;
+
+int main() {
+    int n, inserts = 0;
+    scanf("%d", &n);
+    for (int i = 0; i < n; ++i) {
+        char c;
+        query q;
+        q.type = c;
+        scanf(" %c", &c);
+        if (c == 'D') {
+            int a;
+            cin >> a;
+            q.del = a;
+        }
+        else {
+            int a, b;
+            cin >> a >> b;
+            q.type = c;
+            if (c == 'I') {
+                q.insert = {a, b};
+                inserts++;
+            } else {
+                q.sum = {a, b};
+            }
+        }
+        queries.push_back(q);
+    }
+    for (int i = n-1; i > 0; i--) {
+        query q = queries[i];
+        if (q.type != 'I') continue;
+        int addition = sptree.query(q.insert.p);
+        q_to_pos[i] = addition + q.insert.p; 
+    }
+
+    for (int i = 0; i < n; i++) {
+        
+    }
+}
\ No newline at end of file
diff --git a/Semestr 4/aisd/pracownia4/show_problem.pdf b/Semestr 4/aisd/pracownia4/show_problem.pdf
new file mode 100644
index 0000000..8a1c155
--- /dev/null
+++ b/Semestr 4/aisd/pracownia4/show_problem.pdf
diff --git a/Semestr 4/ask/zadanie1/rozw.c b/Semestr 4/ask/zadanie1/rozw.c
new file mode 100644
index 0000000..068a268
--- /dev/null
+++ b/Semestr 4/ask/zadanie1/rozw.c
@@ -0,0 +1,21 @@
+#include <stdint.h>
+#include <stdio.h>
+
+const uint64_t C[] = {
+    0x5555555555555555LL,
+    0x3333333333333333LL,
+    0x0f0f0f0f0f0f0f0fLL,
+    0x00ff00ff00ff00ffLL,
+    0x0000ffff0000ffffLL,
+    0x00000000ffffffffLL
+};
+
+uint64_t revbits(uint64_t x) {
+    x = ((x & C[0]) << 1) | ((x >> 1) & C[0]);
+    x = ((x & C[1]) << 2) | ((x >> 2) & C[1]);
+    x = ((x & C[2]) << 4) | ((x >> 4) & C[2]);
+    x = ((x & C[3]) << 8) | ((x >> 8) & C[3]);
+    x = ((x & C[4]) << 16) | ((x >> 16) & C[4]);
+    x = ((x & C[5]) << 32) | ((x >> 32) & C[5]);
+    return x;
+}
\ No newline at end of file
diff --git a/Semestr 4/sieci/pracownia1/icmp_checksum.c b/Semestr 4/sieci/pracownia1/icmp_checksum.c
deleted file mode 100644
index c9dc96b..0000000
--- a/Semestr 4/sieci/pracownia1/icmp_checksum.c
+++ /dev/null
@@ -1,10 +0,0 @@
-u_int16_t compute_icmp_checksum (const void *buff, int length)
-{
-	u_int32_t sum;
-	const u_int16_t* ptr = buff;
-	assert (length % 2 == 0);
-	for (sum = 0; length > 0; length -= 2)
-		sum += *ptr++;
-	sum = (sum >> 16) + (sum & 0xffff);
-	return (u_int16_t)(~(sum + (sum >> 16)));
-}
diff --git a/Semestr 4/sieci/pracownia1/icmp_receive.c b/Semestr 4/sieci/pracownia1/icmp_receive.c
deleted file mode 100644
index 07d3b69..0000000
--- a/Semestr 4/sieci/pracownia1/icmp_receive.c
+++ /dev/null
@@ -1,53 +0,0 @@
-#include <netinet/ip.h>
-#include <arpa/inet.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-#include <errno.h>
-
-
-void print_as_bytes (unsigned char* buff, ssize_t length)
-{
-	for (ssize_t i = 0; i < length; i++, buff++)
-		printf ("%.2x ", *buff);	
-}
-
-
-int main()
-{
-	int sockfd = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
-	if (sockfd < 0) {
-		fprintf(stderr, "socket error: %s\n", strerror(errno)); 
-		return EXIT_FAILURE;
-	}
-
-	for (;;) {
-		
-		struct sockaddr_in 	sender;	
-		socklen_t 			sender_len = sizeof(sender);
-		u_int8_t 			buffer[IP_MAXPACKET];
-
-		ssize_t packet_len = recvfrom (sockfd, buffer, IP_MAXPACKET, 0, (struct sockaddr*)&sender, &sender_len);
-		if (packet_len < 0) {
-			fprintf(stderr, "recvfrom error: %s\n", strerror(errno)); 
-			return EXIT_FAILURE;
-		}
-
-		char sender_ip_str[20]; 
-		inet_ntop(AF_INET, &(sender.sin_addr), sender_ip_str, sizeof(sender_ip_str));
-		printf ("Received IP packet with ICMP content from: %s\n", sender_ip_str);
-
-		struct ip* 			ip_header = (struct ip*) buffer;
-		ssize_t				ip_header_len = 4 * ip_header->ip_hl;
-
-		printf ("IP header: "); 
-		print_as_bytes (buffer, ip_header_len);
-		printf("\n");
-
-		printf ("IP data:   ");
-		print_as_bytes (buffer + ip_header_len, packet_len - ip_header_len);
-		printf("\n\n");
-	}
-
-	return EXIT_SUCCESS;
-}
diff --git a/Semestr 4/sieci/pracownia1/makefile b/Semestr 4/sieci/pracownia1/makefile
index 63f9518..5da00f4 100644
--- a/Semestr 4/sieci/pracownia1/makefile
+++ b/Semestr 4/sieci/pracownia1/makefile
@@ -1,12 +1,19 @@
 CC=gcc
-CFLAGS=-g -Wall -Wextra -Wshadow -pedantic -fsanitize=address -fsanitize=undefined
-
+CFLAGS=-std=c17 -D_GNU_SOURCE -O2 -Wall -Wextra
 TARGET=traceroute
 
 all: $(TARGET)
 
-$(TARGET): $(TARGET).c
-	$(CC) $(CFLAGS) -o $(TARGET) $(TARGET).c
+$(TARGET): $(TARGET).o
+	$(CC) -o $(TARGET) $(TARGET).o 
+
+
+$(TARGET).o: $(TARGET).c
+	$(CC) $(CFLAGS) -c $(TARGET).c
+
+distclean:
+	$(RM) $(TARGET)
+	$(RM) $(TARGET).o
 
 clean:
-	$(RM) $(TARGET)
\ No newline at end of file
+	$(RM) $(TARGET).o
diff --git a/Semestr 4/sieci/pracownia1/traceroute.c b/Semestr 4/sieci/pracownia1/traceroute.c
index 9281e4f..0e51c14 100644
--- a/Semestr 4/sieci/pracownia1/traceroute.c
+++ b/Semestr 4/sieci/pracownia1/traceroute.c
@@ -1,3 +1,8 @@
+/* Pracownia programistyczna nr 1 - traceroute
+ * Imię i nazwisko: Franciszek Malinka
+ * Nr indeksu:      316093
+ */
+
 #include <stdio.h>
 #include <errno.h>
 #include <netinet/ip.h>
@@ -23,6 +28,23 @@ void print_as_bytes (unsigned char* buff, ssize_t length)
 		printf ("%.2x ", *buff);	
 }
 
+void debug_received(uint8_t *buffer, struct sockaddr_in *sender, int packet_len) {
+    char ip_str[20];
+    inet_ntop(AF_INET, &(sender->sin_addr), ip_str, sizeof(ip_str));
+
+    printf("IP packet with ICMP content from: %s\n", ip_str);
+    struct ip*  ip_header = (struct ip*) buffer;
+    ssize_t     ip_header_len = 4 * ip_header->ip_hl;
+
+    printf ("IP header: "); 
+    print_as_bytes (buffer, ip_header_len);
+    printf("\n");
+
+    printf ("IP data:   ");
+    print_as_bytes (buffer + ip_header_len, packet_len - ip_header_len);
+    printf("\n\n");
+}
+
 struct sockaddr_in get_sockaddr_from_ip(char *ip) {
     struct sockaddr_in sock;
     bzero(&sock, sizeof(sock));
@@ -71,7 +93,6 @@ void send_icmp_packet(int sockfd, struct sockaddr_in *destination, int ttl) {
     struct icmp header = create_icmp_header(ttl);
     setsockopt(sockfd, IPPROTO_IP, IP_TTL, &ttl, sizeof(int));
 
-    // printf("%u %d\n", destination->sin_addr.s_addr, sockfd);
     ssize_t bytes_sent = sendto(
         sockfd,
         &header,
@@ -84,13 +105,11 @@ void send_icmp_packet(int sockfd, struct sockaddr_in *destination, int ttl) {
         fprintf(stderr, "Error while sending ICMP packet: %s\n", strerror(errno));
         exit(EXIT_FAILURE);
     }
-    // fprintf(stdout, "Bytes sent: %ld\n", bytes_sent);
 }
 
 /* Return ip address of the sender of recceived package */
 ssize_t recv_packet(int sockfd, struct sockaddr_in *sender, uint8_t *buffer) {
-    socklen_t sender_len =   sizeof(*sender);
-
+    socklen_t sender_len = sizeof(*sender);
     ssize_t packet_len = recvfrom(sockfd, buffer, IP_MAXPACKET, 0,
         (struct sockaddr*)sender, &sender_len);
     
@@ -114,36 +133,14 @@ int try_select(int sockfd, struct timeval *tv) {
     return select(sockfd+1, &descriptors, NULL, NULL, tv);
 }
 
-void in_addr_to_string(struct in_addr *sender, char *ip_str) {
-    inet_ntop(AF_INET, sender, ip_str, sizeof(ip_str));
-} 
-
-void debug_recieved(uint8_t *buffer, struct sockaddr_in *sender, int packet_len) {
-    char ip_str[20];
-    inet_ntop(AF_INET, &(sender->sin_addr), ip_str, sizeof(ip_str));
-
-    // in_addr_to_string(&(sender->sin_addr), ip_str);
-    printf("IP packet with ICMP content from: %s\n", ip_str);
-    struct ip*  ip_header = (struct ip*) buffer;
-    ssize_t     ip_header_len = 4 * ip_header->ip_hl;
-
-    printf ("IP header: "); 
-    print_as_bytes (buffer, ip_header_len);
-    printf("\n");
-
-    printf ("IP data:   ");
-    print_as_bytes (buffer + ip_header_len, packet_len - ip_header_len);
-    printf("\n\n");
-}
-
-void pretty_print_router(int ttl, struct in_addr *senders, float mean_wait_time, int messages_recieved) {
+void pretty_print_router(int ttl, struct in_addr *senders, float mean_wait_time, int messages_received) {
     char ip_str[20];
     printf("%d.\t", ttl);
-    if (messages_recieved == 0) {
+    if (messages_received == 0) {
         printf("*\n");
     }
     else {
-        for (int i = 0; i < messages_recieved; i++) {
+        for (int i = 0; i < messages_received; i++) {
             bool already_printed = false;
             for (int j = 0; j < i; j++) {
                 if (senders[i].s_addr == senders[j].s_addr) {
@@ -153,27 +150,25 @@ void pretty_print_router(int ttl, struct in_addr *senders, float mean_wait_time,
             }
             if (already_printed) continue;
             inet_ntop(AF_INET, senders + i, ip_str, sizeof(ip_str));
-            // in_addr_to_string(senders + i, ip_str);
             printf("%-15s ", ip_str);
         }
-        if (messages_recieved < MESSAGES_PER_TTL)   printf("\t???\n");
+        if (messages_received < MESSAGES_PER_TTL)   printf("\t???\n");
         else                                        printf("\t%.2fms\n", mean_wait_time);
     }
 }
 
+// This function decapsulates important data from the IMCP replies
 void get_important_data(uint8_t *buffer, uint8_t *code, uint16_t *id, uint16_t *seq) {
     struct ip*      ip_header = (struct ip*) buffer;
     ssize_t         offset = 4 * ip_header->ip_hl;
     *code = ((struct icmp *)(buffer + offset))->icmp_type;
-    if (*code == ICMP_TIMXCEED) {
+    if (*code != ICMP_ECHOREPLY && *code != ICMP_TIMXCEED) {
+        return;
+    } else if (*code == ICMP_TIMXCEED) {
         offset  += ICMP_MINLEN;
         offset  += 4 * ((struct ip *)(buffer + offset))->ip_hl;
         *seq    = ((struct icmp *)(buffer + offset))->icmp_seq;
         *id     = ((struct icmp *)(buffer + offset))->icmp_id;
-    }
-    else if (*code != ICMP_ECHOREPLY) {
-        fprintf(stderr, "Something went wrong, recieved ICMP packet with code %d\n.", *code);
-        exit(EXIT_FAILURE);
     } else {
         *seq = ((struct icmp *)(buffer + offset))->icmp_seq;
         *id = ((struct icmp *)(buffer + offset))->icmp_id;
@@ -181,13 +176,13 @@ void get_important_data(uint8_t *buffer, uint8_t *code, uint16_t *id, uint16_t *
 }
 
 // timeout in milliseconds
-float get_replies(int sockfd, long timeout, int ttl, int *messages_recieved, struct in_addr *senders) {
+float get_replies(int sockfd, long timeout, int ttl, int *messages_received, struct in_addr *senders) {
     struct sockaddr_in  sender;
     uint8_t             buffer[IP_MAXPACKET];
     int                 ready;
     long                mean_wait_time = 0;
     struct timeval      tv; tv.tv_sec = timeout / 1000; tv.tv_usec = 0;
-    *messages_recieved = 0;
+    *messages_received = 0;
 
     while ((ready = try_select(sockfd, &tv))) {
         if (ready < 0) {
@@ -201,25 +196,29 @@ float get_replies(int sockfd, long timeout, int ttl, int *messages_recieved, str
 
         get_important_data(buffer, &icmp_code, &id, &seq);
         if (seq == ttl) {
-            senders[(*messages_recieved)++] = sender.sin_addr;
+            senders[(*messages_received)++] = sender.sin_addr;
             mean_wait_time += timeout * 1000 - tv.tv_usec;
             
-            if (*messages_recieved == MESSAGES_PER_TTL) break;
+            if (*messages_received == MESSAGES_PER_TTL) break;
         }
     }
     // changing from microseconds to miliseconds
     return (float)mean_wait_time / 3.0 / 1000.0;
 }
 
+// Core of the program.
 void traceroute(struct sockaddr_in *destination) {
-    int sockfd = create_raw_icmp_socket(), messages_recieved = 0;
+    int sockfd = create_raw_icmp_socket(), messages_received = 0;
     struct in_addr senders[MESSAGES_PER_TTL];
 
     for (int ttl = 1; ttl <= MAX_TTL; ++ttl) {
         send_icmp_requests(sockfd, destination, ttl, MESSAGES_PER_TTL);
-        float mean_wait_time = get_replies(sockfd, 1000, ttl, &messages_recieved, senders);
-        pretty_print_router(ttl, senders, mean_wait_time, messages_recieved);
-        for (int i = 0; i < messages_recieved; i++) {
+        float mean_wait_time = get_replies(sockfd, 1000, ttl, &messages_received, senders);
+        pretty_print_router(ttl, senders, mean_wait_time, messages_received);
+
+        // what if our packet branched and we got to the destination faster by some path? 
+        // we gotta make a loop, not an if
+        for (int i = 0; i < messages_received; i++) {
             if (senders[i].s_addr == destination->sin_addr.s_addr) {
                 return;
             }
@@ -234,6 +233,7 @@ int main(int argc, char * argv[]) {
     }
 
     struct sockaddr_in destination = get_sockaddr_from_ip(argv[1]);
+    fprintf(stdout, "traceroute to %s, %d hops max\n", argv[1], MAX_TTL);
     traceroute(&destination);
 
     return 0;
diff --git a/Semestr 4/sieci/warsztaty4/w4.pdf b/Semestr 4/sieci/warsztaty4/w4.pdf
new file mode 100644
index 0000000..1d6b54d
--- /dev/null
+++ b/Semestr 4/sieci/warsztaty4/w4.pdf