From f64f7de412dd06affb0670831bdd117bde33a192 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Tue, 6 Apr 2021 14:28:27 +0200 Subject: Update --- Semestr 4/aisd/pracownia4/rozw.cpp | 121 +++++++++++++++++++++++++++++ Semestr 4/aisd/pracownia4/show_problem.pdf | Bin 0 -> 61345 bytes Semestr 4/ask/zadanie1/rozw.c | 21 +++++ Semestr 4/sieci/pracownia1/icmp_checksum.c | 10 --- Semestr 4/sieci/pracownia1/icmp_receive.c | 53 ------------- Semestr 4/sieci/pracownia1/makefile | 17 ++-- Semestr 4/sieci/pracownia1/traceroute.c | 88 ++++++++++----------- Semestr 4/sieci/warsztaty4/w4.pdf | Bin 0 -> 210974 bytes 8 files changed, 198 insertions(+), 112 deletions(-) create mode 100644 Semestr 4/aisd/pracownia4/rozw.cpp create mode 100644 Semestr 4/aisd/pracownia4/show_problem.pdf create mode 100644 Semestr 4/ask/zadanie1/rozw.c delete mode 100644 Semestr 4/sieci/pracownia1/icmp_checksum.c delete mode 100644 Semestr 4/sieci/pracownia1/icmp_receive.c create mode 100644 Semestr 4/sieci/warsztaty4/w4.pdf 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 +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 queries; +segtreeSP sptree; +map 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 Binary files /dev/null and b/Semestr 4/aisd/pracownia4/show_problem.pdf differ 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 +#include + +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 -#include -#include -#include -#include -#include - - -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 #include #include @@ -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 Binary files /dev/null and b/Semestr 4/sieci/warsztaty4/w4.pdf differ -- cgit v1.2.3